This may probably not be the right place for hardware recommendations but your issue is a bit different to what an average desktop user is faced with.
In general all graphic cards need a driver to work with Ubuntu but not all drivers can come with a default Ubuntu installation because they are not Open Source. Another general rule is that brand new very high end graphic cards may not yet be fully supported, have issues, or need untested, bleeding edge drivers. Very old low end cards may not have a sufficient 3D power to run the Ubuntu Unity desktop.
Intel
Intel graphics is fully supported because the manufacturer provides Open Source drivers for all features. Alas there are no discrete graphic cards with Intel chips available, as the GPU was mostly already integrated.
Nvidia
As you already fopund out newer Nvidia cards may not yet be supported at all by the Open Source nouveau
driver. Therefore we will not easily be able to install Ubuntu. Older cards or low end cards will work, but as compared to the radeon
driver the nouveau
driver still lacks a full support of all features. It may suffice to install Ubuntu but do not expect a fast desktop experience without installing the proprietary Nvidia drivers. Here is a list of supported cards and features.
AMD
Other than Intel the Open Source radeon
driver is quite advanced and fully supports older or low end graphic cards making them fully capable of running Unity. An incomplete list of fully supported AMD cards is maintained on the Ubuntu Community Wiki. This list can be useful when buying a second hand card to plug in for just installing. From the currently available low end spectrum starting with the CEDAR Radeon 5450 we don't expect any issues. These cards should be fully supported by the Open Source driver supplied with the Ubuntu installation DVD and it should run out of the box.
Additional note
There will be no issues using the open source drivers radeon
or nvidia
when switching then graphic card brand but it is not recommended to have proprietary drivers for both, AMD and NVidia running at the same time. Therefore in case you plan to keep a proprietary driver it may be easier to stay with the same brand.