I'd buy an AMD Radeon 4000 series card or newer (but not the high end 69xx, though that's outside your budget).

If you don't care about Windows/DX11 and power consumption isn't a priority, 4000 series may be the safest bet as the drivers have had more time. They can also be found cheap either new or used.

Open drivers of either variety (G3D or not) in recent Ubuntu versions work for desktop effects.