At Present Which is the best choice for a Ubuntu graphics card, AMD or nVidia?
Does not matter, just check the compatibility list before you buy (both make both good and bad cards).
https://wiki.ubuntu.com/HardwareSupportComponentsVideoCards
and also http://free3d.org
Any. Doesn't really matter!
But IMO I would go buy Nvidia as their drivers are more stable on both Windows and Linux as compared to ATI, but if you have a hackintosh compatible hardware and plan to build a hackintosh in future go for ATI.
If you dual boot with windows then ATI seems to be more budget friendly.
If you need help with Hackintosh compatible hardware have a look here see if its possible for you.
But if you ask me, I would go for NVIDIA any day as game developers support it the most.
One way to check compatibility of a given graphics card with Ubuntu is to check Ubuntu's officially certified Component catalog.
From the website:
Canonical and hardware providers certify systems containing the components below.
There you can, for example, search for "5870" (if you're interested in checking compatibility of AMD Radeon HD5870). This specific search will yield No results found., meaning that there is no officially certified hardware containing this card.
If however you're searching for "5450" (for AMD Radeon HD 5450), then you will find Park [Mobility Radeon HD 5430/5450/5470] and a list of laptops containing this component. Unfortunately this is not a definitive blessing for the given hardware component, but it still comes as close as it gets to official certification (some strings are attached). At the very least, it means that it is known to work with Ubuntu.
In addition, you may go to Ubuntu Certification Programme at Launchpad to check if there were reports with issues for the component/laptop that you're interested in.
Lastly, you may also have a list of certified laptops by accessing the Ubuntu Desktop certified hardware.
From the website:
Ubuntu Certified hardware
Ubuntu Certified hardware has passed our extensive testing and review process to make sure Ubuntu runs well out of the box and it is ready for your business. We work closely with OEMs to jointly make Ubuntu available on a wide range of devices.
From that list you can check the graphics cards of supported laptops.