I'm going to vote for no sailing. I have a really hard time seeing how sailing will add anything to the game. The whole point of the map is that the tiles represent regions that can be entered and interacted with. I can't think of a sailing mechanic that won't get boring fast, unless you're going to flesh out all the ocean tiles, make a diving suit and put a ton of underwater content in the game. The other idea I can think of is to make sailing a treasure hunt. You'd find some clues about underwater cities and try to locate them. But as a transportation mechanic it sounds really boring (much as sailing was in Civ).
Let me elaborate a bit on where I'm coming from, then we can go from there or just agree to disagree.
If the world is split up into Continents, and those Continents are discrete chunks of gameplay (they have one Overlord, they have a set level range), I see Sailing as a method of traversing (via the standard overhead map) the "barrier" that exists between the continent you are on and the continent you are headed to. You need to construct a ship to get across the barrier, otherwise if you could walk it... well, what is the barrier?
Anyway, the view I'm coming from is that this is an exploration game. If I start on a continent and just "unlock" a new continent that I can teleport to when I'm done with the current one... well, that's not really exploration to me. That seems more like I'm being linearly fed level-appropriate content to consume, and thus not very interesting.
What I would want
to be able to do is to be able to discover continents, and those continents would be generated as I approach them. Continents could be below my level, or match my level, or be way too hard for my level. I then have a choice as a player of where I want to explore and what I want to break into. I can now also set the Difficulty Level on the fly just by choosing where I move my adventures to.
What I was saying in my previous post about a stripped down Anno style game is just to give different reasons and motivations to go to a particular continent and to make those continents still "matter" once you've liberated them. A high-level continent might have something on it that you really, really want which might make you as a player want to test your mettle and see if you can successfully liberate it. A lower level area might also give you a reason to want to travel there for the same reasons. Since this is going to have some 4X strategy elements to it, I'd like there to be strategic decisions as to where I'm going, rather than just magically unlocking a new continent/port when I've completed the previous one. Of course, Fast Travel options should be given as well once a port on another continent is secured.
It also doesn't have to be sailing. It can be airships that have a fuel range (which could be extended by building certain structures or limited based on a resource that you can acquire). It doesn't matter to me too much about the exact mechanic used, the big thing for me is that *I* want to be the one driving the exploration, I don't want content handed to me whenever I've finished the continent I'm currently on. It's too gamey for my tastes and really misses a big exploration opportunity in a title that bills itself as primarily an exploration-driven game.
Now, I'm certainly not trying to convince you of anything because this is just a matter of taste, but now that I'm posting on a real keyboard instead of my phone I thought I would at least elaborate a little bit on what it is specifically that I'm wanting, and why I want it.