How much ram do you have? If you're maxed out and still slow, then you might consider a dual g4 or g5 to better suit your needs. Or wait a few weeks and see what the new PB lines are going to offer. You could swop a hard drive, but it isn't cheap. It might be worth it to sell your PB and get one more amped.
If you haven't maxed your ram, I'd suggest that. And there are some apps out there such as Cocktail (free) and OnyX which do some maintenance on your Mac which also can help speed up things.
Oh, and what are you trying to do that takes more MhZ? The PB isn't that slow.