First off,
I think Religion (although highly important in the development of history) could be best when just represented by a civ's culture or culture group. Same with language.
OK, now on to the actual suggestions:
1. The ability to claim territory:
(This will require careful AI programming, in fact, the AI should be improved anyway).
With this, your cities get an initial radius for its border (this is the one square radius you start out with in Civ3). As you expand, you build more cities. These will also have a radius of one. You then begin to "claim territory." Whatever territory you claim, that is uncontested, falls into your borders. You can use any of the resources in your territory. In the diplomacy screen, you get to negotiate borders between your civ and a neighboring civ. You also get the ability to name territory (such as naming a jungle "The F***ing Jungle," or whatever you want

)
You may have noticed I haven't mentioned cultural borders, and with good reason. Your territory no longer expands because of your strong culture. Instead, culture can be used to trigger a "golden age." Similar to the requirements for cultural victory, if you have X amount of culture and X times the amount of the second place Civ you become the "cultural capital of the world" and enter a golden age. UU's will no longer trigger a golden age (no need to encourage more war than the warmongering player already has). Culture can still cause cities to defect.
2. Expanded Diplomacy:
2a. Added: Territory negotiation
2aa. You can negotiate territorial desputes in many ways.
-Demands and Concessions. You can demand territory and you can agree to trade "territory section" for "territory section." If you demand a territory that has one of their cities in it, you also get the city. "Territory sections" are usually grouped with a city or landmark (such as a river or mountain range. Although this might not give you the freedom to be a specific as possible, we need something to complain about

).
-Taking it. If you occupy a territory with a city or colony in that territory, you can "annex" that territory and keep it, unless they choose to use force to take it.
2ab. You can also agree to divide other countries (such as partitioning Poland)
2b. Added: Non-agression pacts.
Because of the changes in treaties between Civ2 and Civ3, this can best be compared to the Cease Fire in Civ2. Although I think "trust" is more realistic, we have to deal with the AI. If the AI could be trustful enough (and the Humans who deal with the AI could be trusted enough), this wouldn't be needed.
2c. Intervention:
The ability to intervene with other nation's policies. You can act as a mediator between wars. You can arrange trade embargos. Etc.
3. United Nations:
As opposed to the "el cheapo" victory. The UN is a multi-national orginization that agrees to enforce the common defense, to stop world attrocities, to provide economic aid, etc.
Now that I explained what the UN is, I'll explain what the UN is in Civilization

. After a certain tech (probably Radio) the civ that got the tech first, the civ with the most cities, and the cultural capital of the world (the Civ with the most culture) get to join the UN immediately. Any Civ can join the UN with the majority of UN approval. Likewise, any Civ can withdraw if it doesn't want to follow UN decisions. The UN can have environmental treaties, offer economic aid, trade embargoes, joint resolution for military activities, SALT treaties, etc. This is similar to the Planetary Council in SMAC.
The el chepo victory would be removed, although it is possible to dominate the UN, controlling international politics with threats and allies.
4. Military and Wars:
Although I was originally upset by the changes in the combat system, I now like them, as Civilization is a game, so it doesn't need complicated realism (the simplified combat system is fine). However, I want to change wars.
When the city's last defender is killed and you enter the city you now have 3 options.
-Raise the city
-Occupy the city
-Sack the city
Raising cities is frowned apon after the ancient age.
Occupying a city is just like capturing it, only it isn't perminant.
During wars, resistors can cause cities to flip back, and even can attack military units that are in the city.
Sacking the city is basically doing anything short of raising it. You can sabatoge city buildings, kill population, destroy improvments, whatever (it could give you a list and you choose what you want). Sacking offers seriously less international consiquences (except for pop killing).
5. Peace:
After a war is ended, you get a whole bunch of options during peace.
First, you demand any captured city and even cities you haven't captured. Resistors won't go away during war (although than can be quiet and go back to work for a little while) and will only stop permenently after you stop them during peace.
You can also get
occupation zones
Areas where your military occupies the region and its cities for a specified amount of time, but not control the production or the Civ.
Resistors still exist, but not as much as with keeping the territory yourself
Puppet governments
Governments who are very loyal to you, but not nessesarily their population. They will give you whatever you want, and you can tell them to do things, like research certain techs. You basically control all of their activities indirectly. Resistors can gain strength and re-take some cities from your puppet gov (as they can with territory you own or occupy) they can also settle down and live with the new government (as with Occupation and ownership)
Forced Disarmament
Usually combined with an occupation, these allow you to demand that they keep no military or keep a "defensive only" military. If you choose not to occupy the zone when you have disarmament, consolidating the spread of your military or just simply avoiding resistors, there is nothing to stop the re-build of their army, you'll just have to stop them before/after they do
Of course you get the other stuff, such as techs and gold, that you can demand for peace.
How's that for some ideas?
