A few more thoughts (I may have blanked on some of the previous posts and I've never seen PTW or C3C, so forgive me if I repeat someone's idea or state the obvious):
If you form an alliance with another civ, during wartime your units should be able to occupy the same square at the same time. Also, If one of your ally's cities is overrun by the enemy and you take it back, it should automatically fall back under the control of your ally (as opposed to your having the option of keeping it or being generous and gifting it back to them). If you "liberate" the city of a civ that is fighting against the same enemy but that you are not formally allied with, you can be more devious in your dealings.
Barbarians that attack en masse ("raging" contingents of 20 or so horsemen) that destroy all units in a majority of a civ's cities should have a percentage chance of overwhelming that civ and producing an entirely new -- fully functioning -- civ of their own, instead of just depleting the treasury as they do now. All successful civilizations were originally some other civ's "barbarian" neighbors. We've immortalized a certain few because they were the most successful in reality, but if Civ is about rewriting history, why not give the Goths a chance to rule?
Allies that are brought into a conflict by one main civ should cease fire and grant peace to the enemy civ when it negotiates peace with the main ally (think World War II). Or, alternately, there should be a mediation aspect to diplomacy.
Settlers and Workers should have skill levels (like the military units) but appropriate to their abilities to create or transform: i.e, faster Workers or engineers; or maybe more productive farms and mines; sturdier fortresses; better, more streamlined roads for faster travel; cities that go up larger or with bonus food/shield/gold values for the city square, etc.
Resources and luxuries should be more complicated and variable than 1,2 or 3 of some value. Combined with the above idea of levels of worker abilities, other factors should be added, such as gradual depletion, general productivness, quality (purer vein, more valuable fur, unique varietals), demand, etc. Resources should dwindle, but different caches should have (sometimes greatly) differing starting values (think Kuwait or OPEC versus central California). Some people have complained about resources going away then popping up elsewhere, but that doesn't bother me because it reflects our standard scramble to locate new sources when we start running dry.
Cities in advanced civs should not have their size restricted by their location. Look at Las Vegas and the largest cities of Japan and the Mideast, all of which are very dependent on imports, especially food (internally to a civ definitely, externally to some extent).
Roads and other improvements from abandoned or destroyed civs should degrade and eventually disappear if not encompassed by another civ's borders (think Roman roads nowadays), and it shouldn't take very long.
Completely scrap the tech tree concept (or at least make it invisible). It's utterly ridiculous that you should be able to look ahead 500 or 2000 years to map out your progress. In addition to the "fog of war" there should be a "fog of science" that would let you look ahead very narrowly when you're concentrating on a certain discipline (such as weapons or religion or government). Of course, by now we all have the tree memorized so just making it invisible wouldn't really accomplish anything. Oh well.
Well, I have other ideas but they're even more nitpicky. And it's late. And this post is really long. So, enough.