I'm not that big of a gamer so I don't pay much attention to graphics cards. However, this question pops up quite often: what's a good video graphics adapter for Linux? The recommendation I got from a thread in the forums today: the ATI HD 4890. The suggestion owes much to the open source driver support that ATI provides.
Phoronix has an in-depth review of the ATI HD 4890 on Linux. A scan of eBay reveals that it's pricey, thogh, for me at least: around P10,000 ($200), give or take.