Strange...on my midrange system the game crawled at 1024x768x32. I was getting about 6 frames per second after the second turn. So I can lay Doom 3 on this setup, but not Civ 4. <shrug>
AMD Sempron 2800
512MB DDR 400
Geforce 6600GT
Win XP Home
Might be your low ram. It ran fairly well on my 2100 with a plain 6600, but 1GB system ram.