1) As has been suggested, the civs begin the game neutrally. Building a wonder allows the addition of one trait. Each wonder would only allow 1-2 specific traits, eg the pyramids allows your choice of industrious or religious traits. A small wonder could be added that would allow 1 trait, so no one gets completely screwed.
As far as the special units go, it still doesn't make sense to me that say the Persians would develop a special unit that requires iron if they had no iron, but I don't see any good way to make them undefined at the start without removing the very early special units, which I wouldn't dream of.
2) The army concept needs to be rethought. I can think of two ways to go.
a) Ditch the armies altogether. Leaders become a combatant unit, which still can be used to rush a project. They have a high attack/defense, scaled for the era, perhaps 6/4 ancient up to 35/20 modern. They only live for a maximum of 20 turns. You then have the choice of either cashing them in right away, or using them to cause havoc and risk the wrath of the RNG, then cash them in just before they are about to expire. Also, perhaps milatiristic civs get a bonus on their leaders of +2/2
b) Leave the armies basically as is, but change the way units fortify. First, units fortify in a specific direction, and only get the fortification bonus if attacked from that direction, or the adjacent directions, and if attacked from behing they are penalized. So for example if you fortified facing north, you +25% if attacked from the northeast, north, and northwest, and -25% if attacked from the south - all others are neutral.
Second, adjacent fortified units can band together once a prerequisite tech is researched. The exact way they band together needs a lot of thought. One possibility would be their defenses are added together, with the adjacent unit's multiplied by some factor, say 2/3 or 3/4. In this way it would be very difficult to break through a line of defenders without either bombarding them to heck, or .. tada.. punching through with an army. Again this banding only works in the direction they are fortified. So once the line is broken then it's open season.
Done well this could greatly reduce the stacks of doom.
The same approach could be done with navies.
3) I'd like the type of starting point to be an option on the choose your world screen (Coastal or Land locked)
I hate starting on the tip of a peninsula but that's where it puts you much of the time. Also I'd like to be able to do Quick start directly from in game, so when I don't like the looks of the map you dont have to go through multiple screens to get a new one.
4) I'm not going to whine too much about the AI. In general it keeps from making a fool of itself. However it really needs more than one strategy. Yes, you get your butt kicked when you first make the transition from civ2 to civ3, but it doesn't take too long to figure out what the AI does. Check where your units are and attack the least defended city, regardless of whether there are 20 cannons and 10 cavalry sitting next to it - with napkins neatly tucked in their collars. This works ok when you are on the same continent, but once you've got it to yourself the AI is really tiresome to play against.
What I would love to see is the AI in a dll and the interface released in an sdk. This is not easy to do, but its doable if decided at the outset of the design. This way the AI itself is not exposed (though releasing the source would be nice too), just the interface. The fact is that AI does not sell games, so let the people try to do better if they think they can.
-Leuf
Edit: Forgot one.
5) What happened to getting tech when you capture a city? It was a little bit too in favor of the attacker in civ2, but there ought to be some chance of it, say 1/16th (and maybe 1/10th for scientific civs) like leaders.
Also when a unit defeats a unit that you dont have the tech for, there is a chance it gets promoted to that unit. You can then either use that unit, or bring it back to a city that has a library/univeristy/research lab depending on the unit, and if you can keep it there for X turns you acquire the tech for it.