The problem is "cheap Mac" does not equal anything with a G3 or G4 CPU. I've been looking around, and it seems like even "beige" G3's are at least $200, especially if they come with any useful amount of RAM or any other goodies. A B&W G3 is considerably more expensive. That must be because any G3 or (especially) G4 is a modern, perfectly useable computer - and that doesn't usually come cheap.
So I guess if you want to play with OS X that is not a cheap proposition, at least not by my definition of cheap. And OS X doesn't work with any "G3 upgraded" Power Macs, at least acording to Apple's web site.
If you want to play with linux on a Mac, just about anything with a PowerPC CPU will work OK. Stay away from "NuBus" machines, they will work with linux but it is a royal pain compared to PCI Macs.
I have 2 early (NuBus) Performas - 1 is a 60MHz PPC 601 with 72MB RAM and a 2GB HD, I was running MkLinux with no problem but right now I'm trying to get YellowDog Linux or Debian working on it with some success, too. The 2nd Performa has a 240MHz G3 upgrade card, an Apple HPV graphics card, 136MB RAM, and a 2GB HD, it runs OS 9 quite well. Too bad linux doesn't see the G3 card and OS X doesn't work on G3 upgraded machines or NuBus. But it's still a lot of fun, especially since I've invested about $40 into the whole mess.