VoodooAlert did extensive tests, which showed that the Cards scale quite nicely with increased PCI speeds :

Voodoo5 PCI
http://www.voodooalert.de/de/content/view/171/25/

Voodoo3 PCI
http://www.voodooalert.de/de/content/view/172/25/

(German, translate with Google or alike)

Any overclock can damage the Hardware of course.

IMHO, the AGP overclock still effective, just not as extreme as for the PCI. Still, should yield good results for as long as the Game you're testing is GPU I/O limited.

AGP Overclock usually is performed by overclocking the FSB (thus increasing CPU I/O, RAM and PCI clocks as well)
Overvolting the AGP Bus usually doesn't have any useful effect, at least I never heard of doing helping alot.

Only a few Boards offer full async (fixed) AGP clocks.

Overall :
If you want it safe, don't try overclocking.

Well, there is no really 'hard, known' boundary for safe operation.
Overclocking risks are always specific for an individual System (especially if it's an older Motherboard).

Generally, I would estimate that 70-75MHz are still somewhere in the "should work fine" region (assuming typical ~10% slack in tolerance for continued operation)

Approaching 80MHz on the AGP, things rather quickly get tricky from what I can tell.
Most top overclocks of that time failed somewhere in the 80's, I can hardly recall anyone ever reaching 90MHz on the AGP.

I think it's best to start with 70 and see how much of a difference it makes (= if it's worth to check out 75MHz).

Personaly, I wouldn't go higher than 75.
What could also make a difference is the available Power surplus the AGP System can handle and the used Chipset, but that's all up to live testing.