I have about $100 to spend. (Its all in ebay cards =/) But i have been looking in to some on ebay.Hopefully i will have one by the start of next week.
800Mhz will leave you at 10.4. 10.5 requires at least a 867 (it can be bypassed but you're still going to be running 10.5 on underpowered hardware).
I'd try to get at least a 1Ghz model (the last few G4 iMacs also came with USB 2.0). But again, it all depends on your needs and the cost. A cheaper, slower G4 with Tiger could do you just fine.