First Off, bring the cruiser back. Naval Warfare jumps from pithy destroyers to giant battleships.
Second, a Torpedo Plane. I'd like to see a plane designed for Naval warfare with lethal bombing capabilities. I can understand that Fighters and Heavy Bombers are only support craft and don't have lethal bombing capabilities... this makes sense. What's lacking are the Torpedo Planes of WWII, the ones that sunk ships. Dive Bombers and "Tank Killers" for Land based operations might be nice, but I'm afraid to ask for too much. So please, Firaxis, bring back Naval Aerial Warfare?
Third, I'd like to an Artillery unit that can move faster than 1 space per turn, like we had in Civ2.
Fourth Attack Helicopters like we had in Civ2. I like the fact we can transport land units like AirCav now, that's great! But what about The Helicopters Offensives capabilities?
Fifth and Last, I'd like to see the Caravan/Frieght brought back. Not so we can horde them and rush wonders but rather 1)so we can establish trade routes for things like "beads" within our own borders and 2) so we can enjoy trickles of trade with far away lands early on. I think the Caravn unit represented how difficult establishing trade routes were back in Ancient and Medieval times. Presently, if two far away nations wanted to trade luxuries (trade route to China, anyone?) they couldn't before ocean faring. Nations in between couldn't play middle man in the process, and make fortunes on trade routes through their territories. However, Caravans can make the time-consuming trek across the continent. Another great thing about caravans was that they could ship food from farming cities to industrial cities. Lets face it, in the real world some areas are agrarian, some are industrial. I loved that facet of Civ2, it made a lot of sense!