... Honestly, I suspect you're not going to find what you're looking for. If you asked me for a good card to run Linux on a non-Intel platform I'd almost certainly say "Radeon", as Nvidia cards (with very few exceptions) don't support 3D acceleration unless you're using the intel-only binary Linux drivers. A 9600 or 9800XT (those appear to be the last ADC equipped cards) will certainly be faster than a 9000, but I used to run Linux on a 1.33Ghz AMD with a 7500 (slower than a 9000) and video performance was never an issue. Sure it was years ago but that thing could run Half-Life and friends under Wine at quite high resolutions without breaking a sweat. Are you certain that:
A: Acceleration is enabled? Doing a quick google leads me to think that you may well have it turned off, as it appears to be by default on a lot of different Mac hardware combinations. Try running "glxinfo" and seeing if it actually says you're getting hardware assist. Or:
B: What looks like "video slowness" isn't actually something else? Ubuntu, if you're talking about regular Ubuntu and not Kubuntu or Xubuntu or whatever, has gotten pretty fat. Speaking from recent experience a 2.8ghz Pentium 4 with a Radeon X300 doesn't run it that great and that's a machine that most of the time will be running rings around a G4.
If acceleration works and you're not being ridonkulous with desktop effects or animations the card you have *should* be good enough compared to the rest of your box. I'd highly recommend doing some more fiddling before blowing cash on something that might not help.