Your going to have to work hard to find a system with AGP these days, so it's a pretty sure bet you will have a PCI-e slot on a new motherboard.
Performance wise, I'd browse
this review to see what you would be comfortable with. Not sure how much these cards go for in the UK, but your price range is likely to be with the lower 8600 cards, or the older 7800s. A 7600 isn't going to be a huge jump for you, and anything lower in the 7 or 8 series is likely not to provide much benefit at all over what you have now.
Also, the Need for Speed games also always hit the consoles. If the only use of the card would be for games that also ship on a console, it might be worth a look to grab a Core XBox 360 to still get decent resolutions. The XBox will run on a monitor using the VGA cable, and the PS3 will run on DVI using an HDMI->DVI cable, though I have a feeling the PS3 is likely to be more then you want to spend currently.