Sometimes that is all it takes, rebalancing a few elements to squeeze out good performances. However, that is not always enough.
It sure wasn't enough. Anyone that ever watched a recorded game (with the game recorder from those swedish? guys, that thing rocked) of a good multiplayer player could beat 3 AI's with a boatload of extra resources and a safe build up time without problems. It still sucked
To ever have a good AI will need a scriptable interface that has the interaction possibilities to:
-control all movement of every unit.
-control all production / working of every city
This will allow scripts to be written that make the AI MM its units well. Implement sensible impprovement building to cities. Assuming that YOUR governators use the same AI one could create custom governators for players to use...
-an elementairy understanding of strategic layout of the map.
-an elementairy understanding of the strategic organisation of an empire.
So the AI could play a bit more like a board game.
You can't let the AI play a game of chess in CIV, to many individual moves to make. The problem of the game GO but then even worse!!
If it were somehow possible to reduce all the little things in CIV to a lesser amount of data / a more high level view. Then the AI could make more intellegent human like decisions based on the info.
Of course I doubt if it all can be done...

(the part of creating the tools for the script, if the tools are there i have faith that the script will be there too soon)
Oh, and also keep in mind that the more the Ai has to 'think' the more CPU time it takes up, hence a slower game. That said, how effeciently the program carries out all this scripting may determine the nature of the AI's 'intelligence.'
One nice thing about CIV is that while (allmost) all other games intensify in the graphics department asking for more and more performance, CIV performance is basically fixed. All the extra clockcycles that keep coming every year can be used to futher the AI. I personally dont need wonder movies, the 3d iso terrain of SMAC looked realistic (the fact that higher terain gave more energy wasn't!) but was also very very confusing at times.
As long as the interface for the player remains responsive; I dont mind a few extra seconds wait at the end of turn.