Out of personal experience with older and recent discrete graphics cards, I would generally say that, regardless of brand, if you want better performance and less headaches, just load proprietary drivers, you paid for them anyway.
I had a lot of trouble with three Nvidia cards of different generations on GNU/Linux, however I managed to get them to work properly; while AMD/ATI GPUs andAPUs worked fine mostly - I experienced minor, specific issues with my laptop APU, like desktop freezing when HDMI is disconnected before the multi-monitor setup is manually reconfigured, no big deal. Hardware compatibility problems can be very subjective and need-dependent, they also depend on the combination of components, making this matter even trickier.
Narrowing this answer to fit your particular questions (not really hah), which I guess is the whole point of this thread... I recently built a rig with used parts purchased on eBay, doing everything on my side to make sure they were in good condition. Great stuff for around half the retailer price. Assuming you prefer shiny new hardware, as the cards you wanted were sold out on Newegg,
Tigerdirect is a reasonable alternative.