Slashie,
You should still make sea travel more interesting, but allow the player to opt out of it, delegating the risk to the ships' captains. Further, you may want to allow for several fleets or groups rather than just one, that way you can control some manually and let the others run their course by means of fast travel.
I fear that, no matter how interesting it becomes, it will still be very tedious to travel to and fro the same exact locations dozens/hundreds of times.
Since the game is turn-based, you can choose to have "brain-idle" time at any point. If you look at Mass Effect 2's probe/mining system, it is somewhat fun to do once or twice, but after a dozen times you wonder if, with all of the fancy technology on the ship, sweeping a mouse back and forward can't be automated! It really felt like a chore after a while.
Anno 1404 - Dawn of Discovery, for example, allows you to automate your trade routes after you have discovered/settled a location. For Expedition, though, I would suggest something a bit simpler: being able to give one-off instructions to ships/fleets for fast travel, rather than setting up condition-based waypoints as in Anno.
I'm not too crazy about the more fantasy/mythical approach that yodhe brings up, since I'm certain there is enough richness in this period to have no need of supplementing the theme. However, some sort of wind system or currents is definitely a must in a game where sailing is a major part.
Esc should exit menus/shops as Space already does. I would also like to be able to start the game with preset expedition loadouts, rather than having to go to the stores every single time!
Finally, in the main menu, you may want to hide or gray out the "Resume Expedition" option if there are no resumable expeditions.
That's it for now!
Very excited to see how the game develops.
Ebyan "Nolithius" Alvarez-Buylla
http://www.nolithius.com