[*]Give Battleships and maybe Frigates the ability to cause collateral damage to units on coastal tiles (especially cities); this would definitely make the units more valuable. As a counter, Artillery could gain the ability to cause collateral damage to ships.
Yeah, some sort of stronger bombardment would be nice, perhaps collateral damage without any risk to the ship (as it is, there isn't even a collateral damage promotion for naval units, let alone against cities). Or a small chance to wipe out a building, or lower the population. The coastal fortress might be brought back to combat this, or like you said, simply allowing siege units to fire back at the ships. In any case, just bombing out the city's defence percentage is useless in itself, unless you have an invasion force outside the city. And if you do plan to invade, you might as well use catapults to lower the city's defence %.
Or maybe they should just let you target terrain improvements like in Civ 3. With the threat of someone coming from nowhere and bomb a town back to a cottage in only three turns, then having to wait 50 (or whatever) turns again to get it back to full strength, you'd want to obtain naval superiority.
[*]It might be complicated (or very simple) to set up an equivalent to naval blockades, where you are able to block your enemy's intercontinental trade routes. I'm not sure how to implement this one, though--I never much liked Call to Power's messy-looking trade routes, so I don't want to see that come back.
There is a very simple way to do this. If you put a ship (a warship, not a transport ship or Caravel) on:
1) Any water square within a hostile city's radius
Or if that seems too powerful:
2) A coastal square adjacent to the city square (meaning the ship can be bombarded with siege units)
- it's a blockade! As long as you keep it there, the city earns no income for its trade routes that depend on the water, and no trade of resources with other civs is possible if that city is the only trade network connection to his trading partners (in other words, you might have to put a ship outside each one of his coastal cities to stop him from importing that oil to build Destroyers
). As soon as the ship moves or is defeated, the trading recommences.
Naval blockades of this sort, along with a degree of city/shore bombardment and counter bombardment, would probably be very easy to implement, and would add a lot of strategical depth to the game. As it is now, I can't really be bothered to build ships just to raid fishing nets. It's so petty.