Hmm...
New Cards, that would suit the Performance of a P3 500...
In my Mind, that could be :
PoverVR Kyro II 64MB AGP
(but remember this Card is facing the same non-T&L Restrictions like the 3dfx Cards, so it will probably help you out only for a short time
)
ATI Radeon 8500LE 64MB AGP
(maybe even a bit overpowered for a P3 500, but it should be extremely cheap, and with 250/250MHz, a quantum leap from a Voodoo3. Both in Performance, and compatibility).
Actually the R8500 or R8500LE series is something I will have a look into, when the time comes to replace my remaining Voodoo3/Voodoo4 Cards in the secondary Systems.