I'd like to see unique great works. I mean they'd be like world wonders, would have a movie too, but they'd rather give cultural, great person and such bonuses. Of course only a great artist could create any of these.
There should be more barbarians (especially pirates on the seas!). There should be also not only individual units, but barbarian states as well (I mean historical states which were 'barbarians' throughout their whole history, like vikings). I don't know, maybe these states could be merged with the original civilization design, but they'd be far more aggressive and less concentrating on developing and such.
Vassal states should not always be friendly, and they should be able to start a revolution war against us.
Also, capitulating should not create simple vassal states but something more strict - e.g. we should be able to control whom they can trade with and so on. People love power. I do love power.
Now what about "auctions"? You can make an offer to multiple leaders at the same time, and they'd be constantly going lower and lower with their price to get the deal (of course only to a limit). This should be realistic, though, but would bring some more life in trading.
New civilizations should be: Hungary, Poland, Italy, Venezia (?), Denmark, Finland, Norwegia, Scotland, Ireland, Canada, Austria, Phoenicia (?), Iroquis, Apache, Sioux (yes, break up the native american stuff). There could be fully independent cities too.
Leader traits should be modified to a scaled thing. They'd still have the traits stuff, but they would have all traits and each of them would have a scale of three (or four or five?). That'd create some more diverse leaders.
A new great person: Great Admiral. Should behave like a Great General but on water. He should be also turned into a flagship which would be the most modern ship in the current era but have many extra bonuses (should be upgradeable to newer ship classes too, but with more cost).
Great Doctors? They could make clinics which have plus healthiness in the city and the cities close to it, and maybe some other bonus too. If joining a colony, they'd give + health and science.
Great Workers? I don't know whether we could find enough names for the game of this type, but if yes, they could create some factory with a huge production bonus. If joining a colony, they'd give + production and maybe + gold.
Great Prophets should be able to turn more cities in the vicinity to a chosen religion (wiping out every other religion, and consuming the unit). They could also add that religion to the cities.
Cities should be abandonable, but reinhabitable with some cost which increases with time. Like when England leaves a badly placed city, the German comes in and reoccupy it, paying 100 gold for the repairing of the not maintained city. These cities should disappear after some decades.
Tiles should have some diagonal features to hide some of the blocky nature of the terrain.
More types of tiles, depending on altitude: lowland, plains, low/high hills, low/high mountains. Cannon-eating marshes would be welcomed too.
Rivers should be not between the tiles but tiles themselves. This would (of course) require much bigger maps (so let there be a possibility to return to the old "between-tiles-is-a-river" version) but would make bridge building more fun. You could choose the type of the bridge and have workers work on it.
New terraforming possibilities: tile converting (like desert into plains) -> requires much gold and workforce, and isn't very effective at early ages. With water workers (either normal workers on any transport or with a new worker type?). You could play holland: surround the wanted are with plains or hills, and you have an inland sea. You only have to get the water out of it somehow.
You could build dams. You get some workers, specify the line of the dam, and let them work.
Planting forests should be in the game too.
Canals canals canals!
Accelerated tectonics to make landscape change. You could choose the rate of acceleration in the settings. It's still a slow process.
Roads should have some negative impact (unhealthiness?) to prevent road spawling all over the place, it's very ugly and prevents me from blocking trade routes without a huge army.
Eras: stone age, bronze age, iron age, classic age, renessaince age, (classicism?), industrialism, modern age, nuke age, future age.
Natural disasters (earthquakes, volcanoes, cunamis, asteroids and everything) with graphical representation! Having a message "your countryside was destroyed by a previously dormant volcanoe" is bad. Maybe have a movie like in the world wonders (immersing), maybe not (violating... just think about burning and screaming people near an erupting volcanoe?).
We should be able to name a place when we discover it (like seas, oceans, mountains, and so on). The game would use these names when describing a location (like "your Division 842A Cavalry has been destroyed at the east coasts of Loch Ness!"). You can rename anything ever in your territory (consequently you can change a conquested civilization's names too).
Should be able to create own religions, corporations and organisations (like the UN). When discovering a certain tech, you'd be asked if create a new one of these.
-RELIGIONS-
You can create a new religion any time (after discovering Mysticism the least), but you require a great prophet to do so. You can specify it's name, maybe choose a sign for it, and specify at most five or six properties, with positive and negative effects in balance. These effects could affect the religions spreading rate, be production bonus (either for hammers or breads), health or happiness bonus, and so on. The AI would be creative when naming religions too.
When changing religions, the old ones could slowly disappear, depending how central the city is (I'm not sure about this one).
-CORPORATIONS-
The same as religions, only you need various great people. Like when you have a Great Artist, you could create a cultural corporation, when you have a Great Spy, you could create a spying corporation and so on.
-ORGANISATIONS-
Only a Great Diplomat could create one of these (that unit can also be used for various diplomatic effect, like gaining +10 attitude with a leader). You can specify it's name, maybe a sign too. There are the following details to decide:
Who can join? (inviting, requesting, religion based, civic based)
Joining optional?
Number of leaders (they can defy the resolution, so be careful with many leaders!)
Choosing the leaders (choosing every 'n' turn, no choosing at all, or choosing when certain effect happens (e.g. the original leader goes to war for a peacekeeping organisation).
Vote number (equal, army size, population, land area, power, religious population and so on).
What can it affect? (commerce, war, army stuff, civics, land area, etc)
You could also change these things when the organisation exists but you have to make a vote, and if the majority doesn't agree with it, it won't be done.
The AI names these well just like the religions.
Open Border agreements should have levels:
1.) commerce only
2.) domestic units and explorer units (settler, worker, etc)
3.) military units
Also they shouldn't have to be signed from both sides. I mean, you can pay for open borders with a big amount of gold per turn or something like that.
You could mix immediate trades with turn-based trades. Like you pay for a technology with a resource for 'n' turns specified by the other party.
ADDITION #1: the AI should stop making me tear my hair out! When I get a well-defended city on its knees, and I only have to kill the last (badly injured) defender(s), my vassal comes in with his army (a little too late, doesn't he?) and takes MY city! Disgusting! Make them feel like a little more comradeish, program them so they will HELP me and not virtually fight me. Also let me declare war on them (with a 10 or 20 turn peace treaty).
Yes, I know I could have told them go away from that city by ordering them. I just didn't feel like setting targets for seven vassals. Still, this need to be fixed. Maybe make "comradity" a trait too.
ADDITION #2: about training soldiers: we'd need an Armory building to store various weapons (comes very early in the game). Making weapons (100 at a time) is produced by the normal way (hammers). Then if we have enough weapon in a city with enough population, we can click on a button like the Draft one, choose the unit type (or press cancel), and voila! population is converted into soldiers with weapons. Of course we need to be able to carry the weapons. Maybe with some new land transport unit (caravan?).
Also, be able to reverse the process: it'd be fantastic to make soldiers take down their weapons into the armory and convert back to normal population. This way you won't have a million army if you don't need it, but will be able to quickly recruit it when needed. I don't know how this would work with the promotions: when the soldiers lose them if converted back into population, maybe players won't convert them back. Multipling the unit support cost with two-three could help (that way having an army will be quite expensive, so making them retire would let the economy recover a little bit).
Mechanized armies should be produced still the old way (I think it's rather obvious).
Much more resources! Make wood a resource, too. Make resources depletable. The forests will be depletable too, but unless any other resource, it'll recover if not chopped too many trees down. This gives a maximum in the productivity of a forest, of course.
This system will change the game experience at it's base. Of course make more resource places unless you want to deplete them before 1000 AD.
I have an idea for liquid sources (like oil or gas). There should be a resource map, or easier: make the "Show resources" flag display e.g. oil sources with black lines. This area is constantly going together until there is no more left. You can hurry up the production of oil by building more oil towers but of course the oil will run out faster.
ADDITION #3: now I'm pretty unsure about this idea, but what about a "Ruler" unit? It represents YOU. It should have a low movement range and no fighting abilities at all. It's name changes according to the civics (like from Dictator Montezuma to Representative Montezuma, you get the idea). When it gets captured (like a worker or a settler), you can either kill him/her, imprison him/her, request a ransom for him/her or simply let him/her go.
If you lose your Ruler unit, you'll get a new one in some rounds (it's random, but has min and max) WITH CHANGED AND RANDOM TRAITS (not fully random, your civilization's attributes and current state affect it greatly), until then your country is in anarchy and maybe you can't even command your army (should they follow last orders?). So you better make sure to protect him/her well!
Also, make videos about this! And real-time videos, not prerendered! When you decide what to do, the video occur. I mean, you are sitting on your trone... then your guards are bringing the fallen ruler to you... you look at him with anger, hatred and pure evil... then you stand up, get your sword... The rest of the video should be censured

But, this'd make destroying civilizations a little more fun in my opinion. And if you really hated that person (e.g. he captured 30 worker of yours, or whatever), then it'll be statisfaction. Or you can be merciful and just exile him. I may don't have to mention that your decision will have an effect on the other leaders too. Maybe they'll fear you if you execute one of their rival with brutality, so they'll become your vassal, but (as Yoda said) fear brings hatred => they'll dislike you too.
If you didn't like this idea, what about a simpler one: if you destroy his/her last city, then you get to decide his/her fate, and watch the video.
My point is, make the end of an other civilization more... rewarding. Saying "the xyz civilization is wiped out" is not rewarding. Just let me kill Brennus if I want to.
ADDITION #4:
Those pathetic three on three (or even less) fights are just ridicilous. I want 100 units battling with 100 units! Without a bug. The retreat chances should be increased - I don't believe that soldiers can't just run! The chance should depend on the formation (it was already discussed here, I don't want to write it down again).
The victory videos should be also much more rewarding. The diplomatic victory makes me feel angry. The conquest video is better, but still some improvements could be made.
The speed of the time should NOT change. Or at least be able to turn it off.
Make bigger, bigger maps! And that 18 civilizations limit should be turned off! Not as if my computer weren't sweating from a huge map at the end already, but why can't we have 36, or even 72 civs at one time? Well, maybe 72 is a little too much, considering how slow it already is with 18, but if there is no system limits to this (like it'd cause bugs with more civs), then why not?
Model the whole world with high detail. You could choose the location on a globus kind of thing. You just drag a rectangle over the globus (could be rotated, zoomed, and so on), then you can play.
More world wonders if making bigger maps. Also, when a wonder is completed "far away" before we did, then be able to invest the lost hammer into another building or mech unit or weapon (with a penalty of course, maybe 25-40% should be lost). Imagine: you were building something, but you couldn't finish. Can't you use the parts for something else? The lost hammers represent the work used to convert these parts to the right ones. Of course the lost hammers could be still converted to gold, without loss.
Harbors could be built at riversides.
New buildings: Cinema (modern colosseum), Sewers (behaves like public transportation), School (a smaller University, comes earlier into game), Museum (behaves like Library).
New world wonders: The Leaning Tower of Pisa, The Colosseum
New national wonders: Space Station (increases research by at least 20% but is quite expensive to build)
The Manhattan project should give me its creator some bonus for nukes.
Olympics! Every n turn there is an olympic arranged. There is a built-in organisation to do this. The overall health multiplied with the population of your civilization counts into your vote number. Only those who have an Olympic Stadion (a national wonder) may be voted on. When you win, you'll get a big happiness and trade bonus, but the effect fades over the time. The Stadion could still generate some culture and maybe some great person rate.
Be able to transport people from one city to another, like if you have a farmer city with huge overcrowding, and you want to get those people to a new, empty, industrial city, then do it! Also be able to transport food (breads) with the new transport units.
New civic type: Ethnic. It represents how you behave to foreign people in your cities. The first one should be Racism, which decreases the rate foreigns keep coming in your cities, then there is cosmopolitism (the opposite), and so on.
New border rules! You would have to negotiate for your borders. Cultural borders only counts until your borders "crash". This'd need a revise of the current culture system, because culture doesn't raise the number of your men living in a foreign city. Maybe you could brainstorm over this, I'm tired right now to do so.
Back to terraforming: you could cut a hole in the ground, making sea to flood the lowlands (but only the lowlands!). This could give an excellent new weapon to DESTROY civilizations living on lowlands next to the sea and having natural or artifical dams. And this comes early in the game (but requires tons of workers working for a long time to complete). Maybe this will cause balancing problems?
Two kinds of marshes, a light and a heavy one. The first is not very deadly, but still can "eat" your heavier troops. A knight still can trespass that area, but a tank may not. The heavy one can devour all but your lightest units. So a bronze age civilization can still survive from a modern armor attack (in Civ4 it can't really) if surrounded by marshes.
POSTSCRIPTUM: now I have to buy a new keyboard, this one is frayed

please comment the ideas I was unsure of, I'm curious what you think about them.