I have the same machine that you do, and I was contemplating the 800 MHz upgrade a while back, as well as the 500 MHz G4 upgrade. I ultimately went for the G4 uprgrade, since I felt that my uses would benefit more from Altivec, and they weren't yet shipping the 800 MHz (it had only just been announced).
The price was $300 for the G4, and definitely worth it. There was a noticeable speed boost across the board, even in non-altivec apps. My guess is that you'll be more than pleased with the additional speed of a 900 MHz chip. Powerlogix does fine work, too.
If you haven't already done so, give the machine LOTS of RAM. Going from 320 to 768 MB made quite a big difference for me, even before I upgraded the CPU.
Also, you might consider a 5400 RPM HD. I got the one from Toshiba, since it had the largest cache (16 MB), and it also provided a significant performance bump.
The Firewire G3 PB is, in my opinion, one of the best machines Apple has ever made.