Update: Well, as it happens, there's no supported driver for my system (A Thinkpad R51) with a Radeon 7500. So, it seems that Civ 4 is just not going to work until a new driver comes out - if it comes out.

If you visit this page, you'll find a rather complex set of instructions for getting Civ 4 installed and running. I found a far simpler way. Right click on the screen, go to properties, advanced, then to the driver tab. See that "Update Driver" button? Try that. Worked for me, without all the back and forth described on the linked page.

Update: Well, maybe not. The game runs, but with hosed up graphics. Sigh.