The link koszer gave above has someone recommending a Radeon 7500:
FWIW, I've been very happy with the Radeon 7500 (ADC) upgrade in my Cube. These cards can be installed with no modification, except for the removal of the gate bracket, which you really don't need.But, what is the "gate bracket"?
Power Mac G4 Cube, MorphOS with Style!