My personal experience is with NVIDIA and Red Hat Linux, I have a TNT2 M64 and a GeForce2 GTS and they work flawlessly with NVIDIA Linux Drivers. I had heard about other people having problems with ATI Linux Drivers, but don’t have first hand experience. Both cards are AGP and are couple with Athlon processors.
I’d also heard about other people having problems with GeForce FX 5200 and 5200 Ultra on Linux, and only with these cards. So, if you are on a budget I would recommend a GeForce4 MX, if not I would go with a GeForce FX 5700 or higher. In fact my next upgrade will be a Leadtek GeForce FX 5700 non-Ultra with 128MB
I’d seen the difference between DirectX 8 and 9 cards and it’s huge. I recommend you get one of the newer models.
A friend of mine has a Radeon 7500 and an ALL-IN-WONDER 9700 and they’re great for gaming under Windows, he doesn’t run Linux. I’d done some video capture and edition with the AIW and Pinnacle Studio 8 and I’m very satisfied with the results.
But as I said before, I would rather go with NVIDIA.