For some time now, these rules dictated graphics accelerator choices under Linux:
1.) If you want really good driver support and can afford to run an Intel chipset, you go with Intel's integrated graphics. These drivers are open source, but the specifications they are based upon were now.
2.) If you needed speed and decent non-free driver support, you could go with NVidia. The problems are normally minor enough that the basics could be worked around.
3.) Avoid ATI chipsets at all cost, unless you could tolerate a R200 series card with the reverse engineered OSS driver The ATI driver required of other cards had binary drivers that didn't have a good reputation of being stable or secure. Also, the feature set was severely lacking and would not run many applications (like a wide variety of games under Cedega).
4.) If you could afford to run a much less common chipset, depending on the specific tasks at hand, you might have a great or horrid experience with S3, VIA, etc. At this point, these are mostly all special purpose machines, so typical users never have to deal with them.
AMD has shaken this up by promising to release the full specifications to the latest ATI graphics chips. From this, completely open source drivers can be developed and all the typical problems that have been present in vendor supplied drivers can be fixed as the community experiences them. I would expect that users of these cards can look forward to full 3D support, pretty much all the performance the hardware is capable of, proper suspend/resume support, etc. The 2D specifications have already been released and the 3D and video processing specifications were promised soon. So, in theory, ATI cards should soon be the best supported 3D graphics cards on Linux and roughly compete against the NVidia hardware.
I'll be looking forward to the future and would probably be planning on picking one of these up soon if hadn't just bought a house. Slashdot has some more information on this issue: http://hardware.slashdot.org/hardware/07/09/12/1747202.shtml.