If you're into fiddling with your install, maybe ATI is a viable option, but if you want to be able to throw a CD into your system have have it pretty much just work right nVidia is the best bet.
I want the feature set of the ATI hardware, but that feature set isn't currently available to the Linux user, so people can argue all they like about ATI's superior hardware (but not that much more superior), unless the software support is there, it's a moot point.
I myself am trying to stall my next graphics card purchase as long as I can but it's looking like I myself will have to go with an nVidia card. I'll probably go with a GTX260. Then, the next time around, given the way Catalyst is coming along, it should be good to go in about 6 - 12 months.