What are your intentions with the Linux system?
If you want to use it as a server, get the cheapest card you can get, as you only need text mode. I still use 1MB PCI cards for Linux servers. Works perfect.
If you want to use a graphical environment on your Linux system, I think you're best of with a NVidia card, as NVidia has been offering Linux drivers for quite some time, Ati only started recently with Linux drivers..
Before you buy any card, check what your distro supports, or what drivers for what distro's are available!