The Radeon 7500 is a good all-round card. They're easily / cheaply available as a Mac version, are supported in both OS 9 and OS X, and support Quartz Extreme in the latter. They're also passively cooled, don't run too hot and have an ADC port for connecting to older Apple monitors.
The GeForce 3 is faster but virtually unobtainable, especially the Mac version. Most other cards are either too big to fit without moving the VRM (e.g. Radeon 9000, GF4 MX), too big / power hungry for the Cube itself (Radeon 9700/9800 Pro), or are incompatible with the Cube's AGP 2x slot (e.g. Radeon 9600). The GF2 MX is slower than the R7500 and runs much hotter.
The GeForce 6200 fits and is low power (though will still need a fan in a Cube). It also supports Core Image in Tiger / Leopard. This is about the only PC card worth flashing. Note that as it is a much later card, there are no OS 9 drivers. So in that OS, stuff like window scrolling is choppier, and there is no 3D acceleration for games. Basically, you can have OS 9 support or Core Image support, but not both (only the GF4 Ti does both IIRC, and there's no way that fits in a Cube!).
Personally, I found the 6200 wouldn't wake from sleep. It seemed to work for some others, though the issue was fairly widespread. This may not matter to you. The slightly older FX5200 series, however, worked fine for me in this regard. If going this route, get an FX5500 - the die-shrunk version that is available as a 256MB, 128-bit memory bus model. This is actually faster for gaming than the 6200, but as with all FX models, Core Image support is weak. In any case, it's unlikely you'd want to use such an old Mac for anything that's demanding of Core Image acceleration anyway.
As for CPU upgrades, these are scarce and expensive when they do come up. If buying from eBay, make sure you look internationally to maximise your chances, and be patient.
