bleedblue, your system sounds identical to mine for my first few games of Civ IV. We even have the same video card (which I bought especially and exclusively to play Civ IV). The game ran just fine, though all of my games so far are like malclave's: 7 civs, standard size map, normal speed.
Near as I can tell by people's comments in this forum, the game experiences lag that gets worse the longer you play--basically, the animated units' movements are choppier. (You can turn that feature off, but I kind of like it and tolerate the lag.)
I upgraded from 512 to 1 GB of RAM to help alleviate the game lag. It still happens to me, but now takes longer, and I find exiting the game completely and restarting usually clears it up for quite a while. Or I just go to bed.