I think pursuing a bargain can cause you to overemphasize price as a deciding factor. Once a machine reaches a certain age, the parts needed to upgrade it to something close to modern capability make it at least as expensive as a more recent model.
A processor upgrade (which runs about $200-300) is workable, but not as reliable all around. I wouldn't recommend it for a first mac experience. Get a factory config at least as far as the processors and logic board go. Hard drive and optical drive upgrades are rarely a problem for stability and compatability with software. Realize that upgrading the cpu doesn't help an old system's other parts like pci video cards (there is ONLY one new pci graphics card for the mac that I'm aware of) that are more than one generation out of date. Why would you want to choke any speed G4 with pc100 or pc66 ram? Not to mention that the machine is old and less reliable than a new one should be.
I had recently thought about getting a g4 cube 500mhz I saw for $300. It's easily upgradeable, but only the cpu and drives. The bus on the board is still a slow 100mhz compared to the mini's 167mhz and the ram is pc100 compared to the mini's pc2700 ram. There is no modern video adapter for the cube, either. That plus the warranty on the mini makes the choice clear between the two. The diff in price is a only a couple of hundred bucks at the most.
That's my two cents about bargains...