First of all, you should know what kind of graphics slot you have on your motherboard - AGP8x or PCI-E(E stands for express) (pref. 16x). A little side note: some twisted Asrock motherboards have a hybrid AGP and PCI-E compilation, where the PCI-E is 8x, so you should check wether your motherboard has PCI-E 16x. If you have AGP 8x or PCI-E 8x, buy a new PC (Yes, I have AGP 8x myself at the moment, and that's why I will never buy a new graphics card for my current system since it would be more expensive than a PCI-E and will not give the performance boost for that money). If you have PCI-E 16x, then basically, go out and buy a card. Aim for the mid-end or the mid-high end (~$100-$200). Hardcore gamer cards will do you no good if you don't have your CPU, RAM and Motherboard cut out for gaming - they will bottleneck the card; but if you buy a cheap low-end card, you won't be able to play any games at a acceptable gfx quality/framerate.
Usually, all graphics cards that are made for AGP8x will be working on AGP4x, just slower. I'm not sure about the latest AGP8x cards, but the 7th geforce generation will certainly.
