The beefiest card I'm aware of that is guaranteed to work in the G4s is the 2x/4x AGP version of the Radeon 9800 Pro Mac Edition 256MB. It'll run you around $250, though.
The 9600 doesn't pack quite the punch, but costs under $100, so it's a much better budget-oriented choice.
The thing to watch out for is the AGP speed; the G5s are AGP 8x, but depending on the G4 model they're either 4x or 2x, so you need to make sure to get a card that supports the correct speed for your particular G4. The 256MB X800 Mac Edition is plenty beefy, for example, but it's AGP 8x only, so it doesn't support any of the G4s--G5 only.
You can get into tricker stuff like flashing the firmware of Windows cards to run in a Mac, but I personally wouldn't mess with that.