Funny you should mention... I just finished upgrading a 400MHz B&W G3 here at the office. First thing I did was put in an ATI Radeon 7000 PCI graphics card. That right there increased my graphics speed by over 100% (I benchmarked the computer before and after, of course.) I also put in a Sonnet Encore/ZIF 500MHz G4, so Photoshop performance has definitely improved, and upped the RAM to 640MB, which also helped. One thing this computer still lacks, though, is a faster HD. I wish I had put that in with my upgrade proposal.. but then, any higher and you start getting into the cost of just buying a used G4, so I kept the cost at around the $400 mark.
So, as the others mentioned, my advice is to get two things at the very least (okay, three...):
1) ATI Radeon 7000 PCI graphics card.
2) 7200rpm hard drive.
3) A couple extra 256MB RAM chips in there wouldn't hurt either.
That right there will give you a significant performance boost.