Imo, Naval units will overcomplicate the game world. Only way I see this working is if many changes are made to the game:
A minimalist approach to sea travel would not require to much work or over complicate the game. It would however still add a lot to the game and really open maps up so it is much harder to get cornered. The only major programming necessary would the system to actually enter water. The easiest way would probably just to have auto naval transition where your units and caravans automatically become boats when they attempt to travel over water. A slightly tweaked version of that would have resources called harbors that spawn on beaches, in order to enter water you would need to own a harbor on that body of water.
After that all you would need is some very simple art and tweaks:
-To auto generate some beaches, instead of all cliffs. Which would make maps look much better anyway.
-Make some ocean goodie huts. Like floating chests and drift wood.
-Add a fish resource that would just grant food to the nearest city.
-Add in some boat tactical maps.
-Have pioneers create buoys instead of outposts when on water, which would be un-upgradeable.
-Add in some aquatic monsters and lairs. Abeix could be tweaked to make a great sea serpent, and everyone loves pirates.
This wouldn't be that hard to implement but would add so much to the game. Players would no longer get cornered or stuck behind monsters and other players so much. There would be more areas to explore. Maps would be much more distinct and we could have many new types, and oceans would no longer be made of acid to explain the lack of boats. 99% percent of it could be added in through content. Although with a new elemental game in the works I don't expect to see too many new features be introduced at this point. However I think almost everyone would pay a whole $10 for DLC like this!