Maybe people could hire ships from cities situated along the coast. I don't reckon building cities along the coast should be allowed otherwise players might get an advantage.
Some pirate towns or cities could be made, which raid the coasts. Maybe a possible quest could be used to either help them or attempt to destroy them.
I'm sorry if this has been suggested before, as I couldn't find it anywhere, so here I am suggesting it.