ati has improved quality but nvidia is still the preferred option in linux
i personally recommend you a video card with passive cooling solution, recently i found a ati video card with that characteristic under $50
intel and amd has the same support in cpus, as always
what you can find problematic is the chipset supporting the cpu, as you know newer chipsets will give you problems in linux but this happens in intel, amd, via and sis chipsets