Well, since I'm so late to the party, I'll throw out more than one idea...
Naval movement should be heavily modified. Keep the movement points for each ship, but move on any controlled water like it is a railroad, and unexplored water uses movement points--as you move INTO a square not out of like current. You would use movement points in other civs waters--say at triple the normal cost. Unclaimed water would get better movement bonuses as you got the techs. So with Navigation and modern ships, for example, unclaimed water would be treated like railroads.
You could instantly get an invasion to the enemy waters, but if his boundary extended far enough you may not be able to get to land on the same turn. (Or you'd have to land away from his major coastal cities, like in real life.) This is important since the downside is, ships SINK. Artillery, coastal forts and aircraft should be able to completely kill a ship. (Ships could not kill each other in a bombarment situation unless you wanted to get into the ranges of the guns on the ship types and allow the longer range one to kill one that is out of range of retaliation.) Damage would spread around all ships as normal but you'd sink the escorts first to leave transports to land an invasion.
I'd also like some sort of BENEFIT for building ships--or at least a reason to. Maybe ships don't have an upkeep cost, or you gain 1gpt for each ship per each civ with a harbor as extra trade income. Why did England build her navy and why don't you need it in civ? It's abstracted away into building harbors to make the trade routes, but maybe there should be a factor like you need X number of ships per city per good or resource to be able to get the benefit of what you're importing which would at least force you to build some ships.
I would not like to see air or artillery changed away from red-lining ground units--WWII and Vietnam proved that you could carpet bomb something and still not completely destroy ground units. Reduce buildings to rubble, yes, but dug-in troops crawl out of their holes to defend that rubble.
I do NOT understand why they have that 40 turn no-research tech advance in the game. Especially when you consider that the advancements have an infrastructure component. Edison can 'invent' Electricity, but you need to wire up your country before it does you any good! Engineering lets you build a bridge over a river, but presumably what you were 'researching' was actually getting all the rivers bridged!
So I want you to have to spend as many beakers as it takes to get that advancement and not just be able to put one scientist on the job. If you want to build a forbidden palace you need 200 shields, not just 40 turns! (Maybe GLs should be able to rush a tech, then?)
Finally, I would like to change the build queue so that shields are NOT transferable. You start a temple and switch to a galley, the galley has 0 shields in it, but the game remembers how many shields you had in the temple so you can come back and finish it later! The building will still be standing there half-finished, after all. If they wanted to get really tricky, you COULD allow switching from some buidings to others with little or no shield loss--a Temple or Library or Courthouse, for example, is just a shell of a buidling that you just put to a different use.
