I might be going for the CoreDuo route provided that I'd find a suitable ATI card easily (seems to be pretty hard to get...)
You can find PCIe ATI Radeon cards pretty cheaply and easily on Ebay. Just type the following into the search box on Ebay...
radeon (x300,x550,x600)
...that return a list of auctions with the word "radeon" in the title and one of the three strings in parenthesis separated by commas.
The X300, X550, and X600 were all PCIe cards and they do not have issues with dot clocks like some later cards. I like the "X600 XT" myself.
If you want a card with more power for running more modern PC games, you should look at something in the Radeon HD 4xxx family, but you're going to pay a bit more.
Something you need to be careful with when buying X300-X600 cards off ebay is that some come with a weird connector called DMS-59...
http://en.wikipedia.org/wiki/DMS-59To use one of those cards, you'd need a DMS-59 to VGA adapter cable with if not included with the card, will cost you around $6 off ebay. Personally, I'd look for a card with a normal VGA port.
Another thing to watch out for is cards that only have a low-profile bracket. Assuming you're using a normal PC case, you probably don't want a low-profile bracket.
Here's an X600 XT full height, with a vga port for $16, free shipping...
http://www.ebay.com/itm/?ViewItem&item=251117003349Here's an X600 XT that's supposedly brand new for $22, free shipping...
http://www.ebay.com/itm/?ViewItem&item=380453694988Here's a guy selling a lot of THREE of them for $35, free shipping...
http://www.ebay.com/itm/?ViewItem&item=300744904216