The best suggestion in this thread IMO has been the construction time involved with a Navy.
I whole heartedly would support adding a Navy if this was a distinguishing characteristic; otherwise it will become only like another airforce.
Another thing you could do would be to have 10 levels of improvements, starting at Naval Base: Level1 and going through Level10 (or heck, even 15 or something, depending on how limited Navies would be intended to be), and to develop and maintain levels of ships you would be required to have reached a certain level in this improvement list.
It would give more options for improvement levels, and at the same time, would give yet another interesting aspect for all but the largest nations. Up until roughly 4500 infra you can continue to buy only economic improvements; this would mean that many nations would have to pick between military strength in the form of a Navy and economic strength.
Requiring lots of incremental improvements to fully develop a Navy would add lots of strategic elements into the game that currently do not exist. There are not many "options" with improvements currently unless you are either very small (Factories vs Banks/Stadiums) and very large with Missile Defense vs Satellites.