-- There should be a good, vital reason to not allow your opponent to have command over the seas. Examples are:
---- Water tiles in blockaded cities cannot be worked
---- Coastal bombardment
---- Potential of cutting off overseas trade if all ports are blocked (I.E. no workable trade routes -- same effect as if all roads to another civ have been cut.)
-- Ships resting in harbor should be sitting ducks. Sending a fireship into a crowded harbor ends up with a lot of sunken ships.
-- Ships need to move faster! Imagine an army marching along the coast on a series of roads and a ship traveling along the same coast. Which should arrive first? The ship, of course. However, in every age of this game, the ship is slower than the army! (Along roads.)
-- Carriers MUST become important. Battleships should NOT rule the waves all the way til 2050. To do this...
---- Lethal Sea Bombardment. While I completely agree that bombardment should not be able to completely eradicate a land unit, it is not just feasible or logical that bombardment could sink a ship, it is more common for bombardment to sink a ship than for the ship to sink in combat! In order for naval combat to be either important or interesting, you just need lethal sea bombardment!
---- A half-bomber / half-fighter plane that can fit on a carrier. It's not quite a slick and agile jet fighter, and it's not a massive B-52 either. It shouldn't have the range bomber / stealth bomber nor the firepower, but it should be better at bombardment and worse at combat than a fighter -- and it should fit on a carrier.
-- More units, not just for their own sake, but for a better combat system. The upgrade tree should look like this:
Galley -- Galleon -- Transport
Caravel -- Galleon
These are your transports. Their use is self explanatory. Slightly slower movement, pitiful strength, low cost.
Galley -- Frigate -- Destroyer -- Modern Destroyer
These are the fast and agile ships that harass and maraud unprotected ports, resources, and transports. They serve as good escorts, as well. The final two forms also serve as anti-submarine screens and can be very dangerous with torpedoes. Fast movement, low strength, low cost.
Galleass -- Ship Of The Line -- Ironclad -- Cruiser -- AEgis Cruiser
These are the beef, the backbone of the navy. The final two forms also serve as excellent anti-aircraft defense, and the final form can launch cruise missiles. Good at coastal bombardment, important escort missions, and naval superiority. Medium to high strength, medium movement, medium cost.
Dreadnought -- Battleship
The queens of the seas, at least for a significant time. Lesser ships simply fold to their guns. Second to none at naval superiority and coastal bombardment. Very high strength, low movement, very high cost.
Carrier
Fighter -- Jet Fighter
Bomber -- Jet Bomber?
Heavy Bomber -- Stealth Bomber
The current queen of the seas. Versatile as all get-out, capable of winning just about any match where they get in the first hit. Fragile, though -- they must be escorted. Low strength, medium movement, medium cost. (Note: Just because I say medium cost does not mean they'll be cheap. Just the carrier has medium cost; you still have to supply the planes.)
Privateer -- Submarine -- Atomic Submarine
Annoying little PITA's. Dishonorable, aggravating, and very effective. Hard to see coming, and pack a vicious bite with their torpedoes. Can sink any ship caught unawares. How to capture the power of the submarine is difficult to do without making them overpowered. Quite simply, they should have medium movement rate, medium strength, high withdrawal rate, low to medium cost, and destroyers should get +100% vs. submarines.
Some notes: Galleasses are the first ships to use naval guns. They were large, floating fortresses bristling with as many guns as their owners could afford to stuff into them. They weren't very mobile and, like the ironclads after them, had to be towed to the battlefield. (Well, some of the ironclads.) Also, while we're on the subject of ironclads, THEY DON'T HAVE TO LOOK LIKE THE FRIGGIN' MONITOR! Yes, the monitor was the first successful ironclad and easily the most famous, but no, that
wasn't the most used nor the best design for an ironclad -- it was actually pretty impractical, as it wasn't sea worthy at all! Even if it practically couldn't be dented, it doesn't work well if you have to tow it to the battlefield.
Picture of the monitor. Pictures of other ironclads