I have a Sapphire x850 Pro, I can play all my games on full graphics. AOE III, NFS MW, POP 2 Thrones ...
What I would do is go to newegg. look for a card with:
256 MB mem atleast 900MHz
GPU running at atleast 400 MHZ
12 (now) 16 Pixel pipelines
support Open GL 2.0 and Dx 9.0
and PCIx 16x of ofcourse
generally ATI would be on the top of the list - (sort by price ofcourse

) ppl generally like NVidia better but comparing the features... I feel ATI is as good as NVidia and cheap too