3rd party CPU-cards exist from various companies (Sonnet,Nevertech,etc).
The fastest for OSX use would be 2x1.8GHz single 2.0GHz models also exist.
Most common are Sonnet Encore single-CPU cards with 1.6-1.8GHz. Those can still fetch upto 150Euro on EBay.
500MHz-AGP suggests a DualG4 "Gigabit", those came with ATI-Rage GFX which isn't really that much fun under MorphOS (no 3D) so you might also want to look for a Radeon9xxx with atleast 64MB.
Tip:
Buying a complete PMac that allready has a CPU-upgrade and comes with a decent GFX-card on EBay might end cheaper than just buying the CPU !!!
If you don't want to spend that kind of money:
- get a descent GFX card for that 500MHz G4, will make a quite useable system
- buy a stock "QuickSilver" or "MDD/FW800" PowerMac with good (supported) GFX card and 800-1430MHz (priced between 40 and 120Euro)