Solution 1:

I've used a Radeon HD5450 with Ubuntu with good results. Very nice image, no fan, 1GB memory, good non-gaming OpenGL support, low power consumption, less than $50, no fan, HDMI and DVI output, no fan.

It also has CrossFireX support but why would you use it?

Did I mention that it has no fan?

Solution 2:

Here are some options:

$50 and under:

slightly over $50:

  • Galaxy 43GGS8HX3SPZ GeForce GT 430 (Fermi) 1GB 128-bit DDR3 PCI Express 2.0 x16 HDCP Ready Video Card
  • EVGA 01G-P3-N959-TR GeForce 9500 GT 1GB 128-bit DDR2 PCI Express 2.0 x16 HDCP Ready SLI Support Video Card

I am not sure what slot you have on your motherboard though... so these may or may not work for you.

Solution 3:

If you are buying the motherboard, you can get one with an embedded Intel video card. Any recent Intel video card should be fine.

If you plan for an AMD CPU, then an AMD/ATI card is a good choice. You have significant chances that the card will be supported by the open-source driver, and if that fails for now, you have the closed driver.

With NVidia products, is almost similar with AMD/ATI, with the big exception that the open-source driver receives no support from NVidia.

The page https://wiki.ubuntu.com/HardwareSupportComponentsVideoCards is good but not updated so often. Check the last update date for each of the pages.