For those of you still having problems...
Try using low resolution textures... Tick the box in the options menu.Well, you give up the graphical intensity, yet come on, this is Civ... Who needs graphics, when there is fabulous gameplay...
This highly enhanced my game speed, I also do not use multiple units... Graphics settings on low I guess... (it might be medium thou, I am not sure)
My Specs:
P4 2.6
512 RAM (dont ask for the details)
Geforce 4 440 MMX
Hope this helps.
Oguz