One of the best factory upgrades you can do would be to put in a dual 1ghz from a Quicksilver. This is a superb processor, although I'm not sure if the L3 will work work(I need to experiment in a DA, although it did not work in a low-end QS that I had one installed in).
Alternatively, you can watch Ebay and try to pick up an aftermarket CPU. If you can, look for a Sonnet, although Newertech and Powerlogix are also good. Gigadesigns can be good, but require a lot more "fiddling" to get to work reliably.
Many of these super-speed CPU upgrades are based on 7447A processors. These lack L3 cache, and tend to be somewhat slower clock-for-clock than a comparable 7450-series processor with L3. All 7447A processors will also require a ROM flash to work. I have a Gigadesigns that was advertised as a dual 1.8, although I've only been successful getting it to run stably at 1.6ghz(this processor has been tossed around somewhat like a hot potato between members here). Mine benches about the same as a dual 1.42 MDD.
Arguably, the "king" of these aftermarket upgrades is the dual 1.8ghz Sonnet. I have one in a Digital Audio. It's superb, and as a Sonnet it's more or less plug and play(save for the ROM flash required to get it working). The Sonnet variant will boot in OS 9, although not all of these processors will. The nice thing about the Sonnet is that-unlike the DA-you don't have to mess with jumpers and DIP switches to set the voltage and clock speed-just flash the ROM, drop it in, and it works.
I also have a "hotrod" DA that I bought from another member here that has the Newertech 2.0ghz Single processor. Working from memory, I think this is actually a 7448 and not a 7447A. It's incredibly fast. To my knowledge, it's the fastest G4 upgrade available(short of crazy overclocking experiments some do-most upgrades are overclocked at least to some extent).
One other thing to look at is upgrading is your current video card. If OS 9 performance is not important to you, a card that supports Core Image will boost OS X performance considerably(especially in 10.4 and 10.5). Most Core Image cards will require taping pin 3 and 11, and some of these can be iffy in a DA or QS. My main Quicksilver has a Radeon 9600XT from a G5 with the pins taped and some other modification to supply ADC power(basically I cut some "fingers" off an old ISA card and soldered them via a couple of short jumpers to the ADC power tab on the 9600). I have another QS that's running the 9600 Pro PC&Mac, although this card can be iffy in QS and DAs.
My "Hotrod" DA has a flashed ATI FireGL X3, which is a really popular card around here and flashes well into an X800XT(one of the fastest Mac AGP cards). This card is 100% reliable with the pins taped in an MDD, but very iffy in a DA or QS. I have one I flashed myself that I can't get to work in a DA or QS. Other members here have been through two or three of these cards with the same result. The one in my DA was-I think-bought from an Ebay seller who sells them pre-flashed and works perfectly, but others on here have bought from that same seller and can't get them to work in their computers.
There are a lot of other GPU options, but these are just two that I have experience with.
