Hey!
I have exactly the same setup except I'm now running OS X 10.3.7.
I do also have the same problem with performance on "heavier" video files. I do understand the problem is with the processor speed. However I also beleive it has to do with Mac OS X requiring "a lot of juice".
Just for testing I installed VLC on a (somewhat similar to our G3s I'd say) Pentium II machine with 192 MB RAM, a GeForce 2 MX 400 card with 32 MB RAM runnnig Windows XP SP2.
A movie file that my G3 couldn't handle played flawlessly on the above PC...