Agreed--10.4 Tiger. Runs well, you've got plenty of RAM for it, and can handle a modern version of Safari (you do need to download it separately, though--Software Update didn't give it to me automatically when I set up a 10..4 machine recently).
Leopard isn't supported on that machine, and while you might be able to use a hack to get it installed, it's probably not worth the hassle.
If you replace the internal hard drive, the easiest procedure is probably to get an external FW case for the new drive, format it, use Carbon Copy Cloner to clone the old drive to the new one, then swap them. Should just boot at that point, and you can then Archive and Install Tiger when you get a working optical drive/are ready to.
Keep in mind that your iMac probably doesn't support internal drives larger than 137GB--I don't think anything in the G3 era did. No point in buying anything bigger than 120GB, not that there's all that much available in ATA drives anymore.