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.
This document explains how to install
and use the open-source radeonhd
drivers on Ubuntu. This shouldn't be
necessary... unless you're having
problems with the open-source
"ati/radeon" driver that comes
pre-installed with Ubuntu.pre-installed with Ubuntu.
https://help.ubuntu.com/community/RadeonHD
EDIT: As JanC pointed out, you shouldn't install the RadeonHD driver if the pre-installed driver works.
Best Answer
I have a 5770 XFX XXX 1Gb RAM, and in my experience the answer is: no. After taking a look at the official documentation the answer is still no.
The thing is that the radeon driver package, a.k.a. the open source driver for the ATI vga, offers some support for the oldest cards, for the new ones there are two main option:
the fglrx package that basically contain proprietary driver but packed by the Ubuntu team ( tipically outdated package )
the, so called, fglrx ccc AMD ATI proprietary closed driver ( that are the most updated drivers and probably the right ones for your card )
Downloading and building your own package from the latest driver available from AMD ATI is a pretty easy task http://wiki.cchtml.com/index.php/Main_Page and gives you good performance.