8x cards will step down to 4x just fine. Below that, and power issues might come into play with what voltages the slot provides.

What price range are you looking at? Don't just go off of how much memory a card has, as there are 128 cards that will probably run the game worse then whatever your existing card is.

Radeon 9500 and above is a good choice, as is the NVidia lines above say the 5600ish cards.

It's a shame both companies believe in paper launches again. NVidia announced a good midrange card, the 6600, but it's really hard to tell when you might actually see one in reality. On the high end, I have yet to personally see an x800 or 6800 anything in retail stores in a top 100 market city.