Really, landing was not hard, you only need a little beach. The only thing could do impossible to land would be an army... and even then, you can sail some hours more and land far away... I think they would be no restrictions on where land (aside the existence of enemy armies)
About the speed of sea travel? Fast. At least faster than by foot.
A Question... The sea travel will be 'oceanic' or all the sea-regions will be coastal? (I, personally, like the last option better!)
mmm...
Another thing. If you can embark only on a harbour... this mean an army who land on a enemy region/realm will be 'trapped'! If they can't take a city or a town region they will never be able to 'come back home'?
IMHO in a harbour would embark all kind of units, and in a non-harbour region only infantry? or small infantry units? ...or at least nobles without units.
I am expecting coastal. The middle age people couldn't build any ships to travel on oceans.