I am not sure that that arguing for supporting only built-in video is a good idea, it leaves us with relatively weak GPUs.
As to whether or not we have the CPU power, I used to use a Radeon 9500Pro on a 1 Ghz Athlon XP. I don't think G4 PPCs with similar or faster clock rates would have any problem handling the 9500/9700/9800. Also, if you scan Ebay, you'll find these cards are quite common. They're as easily obtainable as the other Radeons currently supported.
As to Andreas mention of even more advanced ATI cards, I didn't dare to bring those up because I was afraid that I'd be asking too much.
I have a Diamond 4650 AGP video card in an AM2 motherboard in own. It's a remarkable board and the 3850 Andreas mentioned is actually slightly more capable.
Even the 3650 (also available in AGP) isn't a bad card. It bests an Nvidia 6800 in most benchmarks.
There are a lot of good ATI based AGP video cards out there and the prices are quite reasonable.
I only mentioned the 9800 family because it ought to be the easiest to implement.
But Andreas is right. We don't need to worry about not having systems that support PCIe.
many manufacturers still produce up to date AGP cards.