Crucial have a system scanner that give certain recommendations for graphic cards and motherboard compatibility. When it comes up with a result, check places like Ebuyer or Novatech for better prices, on the same product . Not sure whether this is the correct link, but you could try it click here
Yes any AGP card will do. The only thing that may concern you is if your power supply is up to it. If you buy a reasonably powered graphics card it will probably require a power connector as well as the power it can get from the AGP slot. Apart from that concern any AGP card will work fine.
and on the specs of the rest of your system. there's no point in putting a £400 graphics card in a pc if one of the other components bottlenecks it.
the x800gto the Crucial scanner suggested for you is a pretty good option unless you're wanting to play the very latest games with all the details and lighting effects on max. You can get one for less than £160 though (Low or Ebuyer for instance) Nvidia alternatives are the 6600gt or 6800. (£110 and £140 resp.)
Let us know about the rest of your system and what you need it to do. A mobo upgrade may require you to replace the CPU and memory.