Anything with Nvidia tacked on to the start. The ATI drivers are reasonable when they work but Nvidia updates more frequently and the linux drivers are on par with the Windows ones. The Nvidia devs take an interest in the linux community rather than just port the driver.
The ATI 9800 is getting on a bit, if you're looking for a good mid-range card I'd suggest a Geforce 6800 Ultra or maybe a 7300. The 7600 is the ultimate "budget" card IMO but it's mid-to-high range rather than mid-to-low. A good quality 6800 will run just about anything you chuck at it and well. Something to note is don't just look at how much memory it has, a 256MB card running at 350MHz isn't as good as a 128MB card running at 500MHz. Shop around and take in the information.
As to whether it will fit, 99% of current video cards are either AGP or PCI Express and it depends on your motherboard as to which will fit. Look up the site for your mobo, it'll tell you the info you need
