My question is, can I buy a new graphics card with a higher AGP speed
than the original AGP2? Are the new cards backwards compatible as far
as the AGP speed goes? If so, any recommendations?

You can use any card that is compatible with a 3.3V AGP slot. I'm not sure
exactly what will happen if you try a card that only wants to be in a 1.5V
or 0.8V slot, but my intuition tells me that it wouldn't work out all too
well.