Well, I guess I'll through my 2 gp into the debate...
On ships: the technical difficulty of adding ships as strategic or tactical units has already been pointed out, although if there were a way to overcome these problems (possibly for a potential Dom III), then I agree that it would be pretty cool to see monsters coming up out of the waves to board your ships...
The problem of ownership could be settled by treating ships much like stealthy units, except that they wouldn't be able to attack an underwater province (unless they could breathe water as well), but they
would run the risk of being discovered and attacked by the underwater residents of that province (or by enemy fleets). The 'owner' of the province would be whoever controlled the underwater portion.
As far as buildings and such allowing 'abstract' use of ships, I don't really see the need. Not only are most of the cultures used as a basis for these nations drawn from an era when ocean navigation was not possible (or at least, not reliable enough to risk an army on), but there are already several nations that
can enter sea provinces, plus the new Water Cult theme... so if you really want to fight in the seas, you've got lots of options.
There could be a few more small things added though... for instance, I could see a national commander, for nations like Pythium for instance, who's a skilled navigator, and can carry his army across seas like the Vanir do... or perhaps a Death spell that summons a 'Ghost Ship', allowing the casting mage to do the same.
I'm afraid I don't really like the idea of improved castles either... mostly because it takes away from the choices you make when designing your nation. Who's going to spend 150 nation points on a great fortress when you can get the same effect by merely spending gold in-game? The same goes for economic buildings really... these things are abstracted into such concepts as dominion scales (one could assume that a strong Order dominion encourages the building of mills and other economic structures for example), starting castle choices (for the administration and supply bonuses) and the 'natural' resource and tax base of various provinces (these places aren't virgin wilderness after all, they do have some infrastructure... you just don't have to mess around with building it yourself).
Formations are another cool idea, but I can easily see how difficult this would be to implement. For one thing, the major counter-tactic to most of them is to break up the formation. The coding for that would be a nightmare... how would the game determine when your shield wall was sufficiently mixed up that it no longer provided its bonuses? Would it happen gradually, or all at once? Also, you'd pretty much have to start accounting for things like which direction a unit was facing when it was attacked... and that's a pretty serious mechanic, especially for something to add in a patch. Would fatigue affect the bonuses you get from formations? What if your squads aren't composed of all the same types of troops? Can mindless troops use formations? Etc., etc....
It's not very often that I argue against the inclusion of new features in a game, but in some cases added complexity breaks more than it 'fixes'. This is especially true when it comes to programming the AI to use these elements... if not done carefully (and preferably in the very early stages of design), it is incredibly easy to 'lobotomize' the AI by adding features only humans can use properly.