I've bought the Nvidia Geforce GT 620.
The GT 620 is a 2012 card, and at the lower-end card so it's affordable, but still performant at 11.2 gigatexel/second fill rate - and it supports multiple monitors on the different outputs (HDMI, DVI, VGA).
So far it works fine. I've got two identical monitors one on the HDMI and other on DVI, and and the colors seem slightly different at factory default settings.
It seems the main thing is to avoid Quadro cards on linux - GeForce cards work fine.
The answer is a little complicated, but goes like this:
Nvidia's open-source driver is really bad (thanks to them being stubborn), but their proprietary driver gives pretty much the best performance of any GPU on Linux.
AMD's open-source driver is better, but still not really good enough to match your investment in a modern video card, so you'll end up resorting to their proprietary driver, which is not as good as Nvidia's.
So: if you're serious about wanting to go entirely open-source, AMD is a slightly better option (though still dissatisfying -- honestly, Intel graphics are probably the only ones whose open-source driver compares well to their Windows performance nowadays, and that wasn't true until 2012), but if you're willing to use proprietary drivers, Nvidia is best.
Note that this assumes that you're using <5 year old hardware, willing to spend north of $100 on your GPU, and have some interest in modern games.
Best Answer
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