You mentioned above that you don't have a PC with AGP, I was in the same scenario and just picked up an old dell PC off ebay for £6 and used that for flashing.
Get a Radeon 7500. I have one in my Cube, it works great. It is also ADC, if taken from a Quicksilver G4 as mine was.
The only caveat is no backplate unless you mod it. No VRM move needed. It works decent in Leopard as well as OS 9.
I picked up a 450MHz Cube in excellent condition recently, with the 22-inch Cinema Display and fully kitted out with 1.5GB of memory. However with the Rage128 card it was pretty much unusable with OSX Tiger.
I managed to track down a proper GeForce2/MX with ADC connector on ebay for $20. It was listed as an "Apple P40 Nvidia 32MB" with serial numbers: 600-9144 630-3799
It fitted in perfectly, replacing the stock Rage128 card and reusing the same back-plate panel. The upgrade made a noticeable difference to the speed of the machine, allowing Quartz Extreme to run and taking some of the load off the CPU.
I've also got a suitable Radeon 9000, but the machine is in such good condition I'm not prepared to take a dremmel to video output to accommodate the additional width of the DVI + ADC connectors or move the VRM just yet.
I got a similar GeForce2/MX, but that runs very hot, to the extend that it freezes. I have a fan but that only hits the processor board and its heatsink. The warm air caused by the MX can only escape through little holes in the top of the Cube. With the case removed it runs smooth.
I just ordered a Radeon 7500. Hope that it doesn't get so hot.