I had similar symptoms, but it turned out for different reasons that had nothing to do with Civ4 (other than that was where I first saw it). I promised myself that if I found the solution I'd post it here, in case anyone else was suffering through this as I was.
CONDITIONS:
Windows XP Home, SP3. ATI Radeon 9250 with 256MB. Black screen, as if it were beginning the map, even showed the "he's over there" icon that shows the direction to the active unit. Mouse cursor worked fine. But everything else froze there and after a few seconds my monitor went to sleep. [Alt-Tab] would bring me back to my desktop, and going back into the game would often bring up the initial play window, but it would freeze again. Also, EVERYTHING was slow, even Windows Explorer and Firefox, simple things. Obviously a video problem.
Ran dxdiag. It showed my 256MB video card as having "n/a" for memory. Direct3d was disabled and could not be enabled. Downloaded and reinstalled DirectX 9.0c from Microsoft.com, reinstalled video drivers from the CD that came with the card. No help.
PROBLEM AND SOLUTION:
It turns out that apparently the latest drivers from ATI do not support AGP hardware acceleration, which my mobo uses. Chased this down on another tech support forum. The most stable ATI drivers that support AGP is Catalyst 7.7, available for download at
http://ati.amd.com/support/drivers/xp/previous/radeon/radeonxip-cat77-xp.html . So in order to fix the problem I had to go find and download an *older* driver package than that which had come with the card. The good news was that because I d/l'd not only the driver but the "Catalyst Control" package, after install it went and configured my system for optimum drivers. I noticed the difference in speed immediately, but dxdiag said I still had no Direct3d. Rebooted and viola, problem gone.
I suspect I know now why so many people buy NVidia video cards instead of ATI. Anyway, I won't say if it helps another person it was worth it. It wasn't, it was over a week's worth of hassle getting my computer back. But I can at least hope that some other poor sap out there will be able to solve his issues the same day they happen.