Open source graphics card options?

An Intel GPU would fit your constraints, but Intel doesn't produce any discrete hardware, so it's only an option if you're buying a new motherboard or CPU.

Why are you discounting nVidia and ATi hardware? They're basically the only discrete GPU hardware vendors, and you're unlikely to find any hardware cheaper than a low-end ATi GPU (for example, this Radeon 3450 from newegg). It's difficult to find second hand hardware as cheap as that once you include shipping.

All modern ATi and nVidia hardware will drive two displays. The only thing you need to look out for is the type of connectors - if you've got two DVI monitors, you'll need to ensure any card you buy has two digital outputs.

I'd recommend an ATi graphics card - the open source drivers are generally good, and AMD releases the documentation so new cards can be supported reasonably quickly. I bought a Radeon 4350 card for about $30 and it works flawlessly with Ubuntu 10.10, including compiz.

Additionally, if you want to go for more than two monitors, ATi “Eyefinity” cards can support up to 6 monitors - although all but one have to either connect using DisplayPort or use DVI and an active DisplayPort→DVI connector.

Many Nvidia cards should be fine, thanks to Nouveau. http://nouveau.freedesktop.org/wiki/FeatureMatrix has some details.