You could use either PCI or AGP.
AGP has some benefits for video cards, like being able to use the system memory for 3D textures. Most of the real world performance benefits are in 3D, like video games.
PCI is just fine though, the actual performance difference between PCI and AGP is usually pretty hard to measure unless you're in a 3D video game, and then it's not all that much, and it depends a lot on what you're doing.
You should search on the internet for G4 video card benchmarks, somebody probably has a chart somewhere.
If you get a PCI card, you can have both your existing card and the new PCI card running and have a dual monitor set up (if you've never done it before, dual monitors are *really* neat).
If you don't want or care about dual monitors, then keep it simple and replace your existing video card.
Either PCI or AGP is going to be a lot faster than the card you already have.
I might add that if you're looking at playing video games, you might look at the comparably priced NVidia GeForce model, as they have, in general, a performance edge over comparable Radeon cards. NVidia is usually pretty good with driver updates too.
