Or they could add biplanes!
My Civ3 mod had bi-planes as the first air unit - they acted similar to Airships, except they could, of course, intercept each other.
The problem is that intercepting airships is possibly the most ******** Civ military concept ever. Might be worse than Spearman>Tank. Well, not quite, but close.
To fix airships, add intercept, and change them to bi-planes. Oh, and they need to move a bit down the line in the tech tree...
The key to naval combat is elegance.
Subs should do moderate damage 16, +50% on attack, have 2 first strike chances and 50% withdrawal - they should also be slower than regular ships. They should be invisible to all but destroyers/CG (guided missile cruiser). This also means subs cannot see others subs, and cannot ATTACK other subs. WW2 saw almost no sub on sub action, simply because the torpedoes were unable to maneuver and subs only able to see surfact targets.
Destroyers should be maybe 24, +50% attack (not defend) against subs. Fastest unit. Also, 30% intercept aircraft.
Battleships should be 40. 10% intercept. That's about it!
Carriers... defend only strength 24.
Guided missile cruisers - 32, 60% intercept, can see subs.
Nuclear attack submarine - 32, 2 first strikes, 50% withdrawal, move as fast as a battleship, not quite as fast as a CG/Destroyer. Can see and attack other subs.
This gives you alot to work with - subs are geared toward attack and withdrawal (duh, just like real life), destroyers as AA picket and ASW, carriers as floating air stations and power projection, battleships as juggernaughts of the seas, and CGs as AA and general force protection.
This will allow someone to create an effective naval stacks/armada, but also gives the attacker the initiative and upperhand in combat - two stacks of equal strength, the advantage, though not overwhelming, goes to the one with initiative.
A force might first attack with a couple of subs, weakening some units, come in with some aircraft, then move in with battleships/GMC - it won't be bloodless for the attacker though. This also gives the active sub hunter the advantage when poking around with destroyers around a convoy, but a destroyer minding it's own business will stand a great chance of being sunk when attacked by a sub.
A lone battleship is just like the Bismark - toast. It cant take alot of damage, but it leads with it's chin. However, give it an escort or two, and bring it in tight for hand to hand when in range.
As air power develops late in the game, battleships will become rarer, and you'll have far more SSN/CVN/CG/DDG stacks.
Some flava:
Also, one might consider enabling a single guided missile capacity for the BB and CG.
A Corvette for light scouting and ASW is a good unit, I had one in Civ3, best speed, give it decent withdrawal chances, good for a skirmishing naval unit.
Amphibious carrier - can carry two helicopter and two marine units. This is a sweet little unit to have. Chopper can be attack or ASW (if you do it)
ASW helicopter - if you create it, you can allow the LHA (Amphib carrier) and GMC to carry one. Range 8, can detect subs. Might need special attack rules, as you don't want it to get a 100% kill, but it also shouldn't be "shot down" by a sub either. Perhaps can bombard to 100%, but only X number of rounds, whatever...
Well, that was just off the cuff, but by using the Civ4 special combat gadgets, you can get really interesting interplay in naval warfare that encourages you to build combined arms fleets and take an active interest in what's over the horizon, lest it come up and knock your fleet down...