for about the 100th time:
I have:
PB G3 500, 384MB RAM, 8MB VRAM. 10GB HD
So I have pretty much the exact same spec as you.
10.3 and 10.4 take up ate same amount of HD, and I am running 10.4.1 absolutely fine. I'd recommend that.
Don't expect too much from H.264, but all the other codecs are fine.
A clean install (of either) is a must. You have nothing to gain from keeping the classic system - but you may want to back up the classic folder you own (and of course all your documents).
I have the luxury of 2 Macs at the moment, and so can back-up clean install on this PB very easily.
10.4.1 Is really good - go for that.
If you need proof of how good it can be, check out the "Top Tiger Tip" in my sig.
P.S. You will find 10.3 and 10.4 faster than OS 9 after a clean install.