You might not need to reinstall.
99.9% of problems with Macs can be solved by resetting the PRAM.
Resetting your Mac's PRAM and NVRAM
I think the only time resetting the PRAM didn't work for me, I took the side of the case off the G5 and there was a tiny reset button. I pressed that and everything worked flawlessly after that.
Hell, sometimes it's a good idea to just occasionally reset it for the hell of it. It fixes all kinds of stuff usually. I've had people tell me their network was slow, or it would boot slower than before, or other various problems; all of them were fixed by resetting the PRAM.
Give that a shot first before you format and reinstall.
I suggest going with Mac OS X Tiger (10.4). It will run the best on G4s. You really need a G5 or Intel Mac to be able to handle Leopard.