I used ATI radeon cards for a long time. The proprietary installer works, but only gives you about half the performance of what the windows drivers do. I switched to nVidia on all boxes and it works a lot better for me. Their Linux drivers give about the same performance as the windows versions, so I'd say a doubling of performance is achievable.
The installer may not be as slick as ATI's, needing to be run in text mode, but that is function over form, which I prefer anyway.
If eBay doesn't do it for you, a 6200 can be found at newegg.com for 30-40 bucks.