It depends upon how you look at it.
If you choose an 8x card, all that will happen is it will operate at the highest speed your motherboard can support.
It is likely you will have to change the graphics multiplier in the BIOS, after you fit your new card.
Look at the reviews for the sort of money you wish to spend and choose appropriately.
Keep in mind, many cards are now available both as AGP and PCIe, so make sure you order the correct one.
As a general rule, a card with more on-board memory will out-perform an identical card with smaller memory.
There are some really good deals about on slightly older cards (last generation) with 256MB of memory, so keep an eye out for those.