Just my 2c worth,
h264 playback on my dual 1GHz G4, up to about 1100kb/s is good, 24 fps with no issues. If I go up to 1800-2000kb/s, audio starts to get choppy. This is under OSX 10.3 and QT7, with 2GB RAM and nothing else running. Reckon on a 700MHz/800MHz G4 to be half the speed of my PMG4 (My PMG4 takes exactly the same amount of time as my PBG4 @ 1.67GHz so half is about right for single CPU).
Like all the others have said, I really was surprised at the CPU requirements when I first started using h264.
Tiger, or Panther on your G4 would make the world of difference, for playback anyway. You could get pretty decent quality, 600kb/s or maybe more at 24fps. Do you have any control over what the video is encoded at ?
Encoding h264 on a G4 is as painful as it gets. About 12 hours computer time for 1 hour of video and audio at 1500kb/s. My Mac Pro can do the same encode in 6-7 minutes.