If it's a KM400 chipset, which it would ne, if the graphics is "Unichrome" and not "ProSavage", then it looks like it's an 8x slot so it would take advantage of higher AGP transfer rates with an 8x card (though there really isn't a lot in it between 4x and 8x ... it's a marketing badge more than anything, as getting data to the card twice as fast, only helps if that was the limit in the first place).
If you are not confident/competent with anti-static protection, I'd recommend going somewhere where they will fit it at a not too extortionate fee.
Going from onboard to 9800 Pro, you'd certainly feel the difference (and the price!). http://www.ebuyer.com/customer/products/index.html?action=c2hvd19wcm9kdWN0X292ZXJ2aWV3&product_uid=47511
9800 Pro example
Also worth looking at DABS, and any other online computer stores you can find - not sure if PC World do fitting instore at a reasonable rate, and they do have some plain-boxed OEM parts (cheaper than glossy retail) in the parts centre.
And check some reviews http://www.tomshardware.com/graphic/20031229/vga-charts-09.html
You want Halo? - you got Halo! - how do they rate on it?
Halo can run in DX9 mode, or DX8
For tests like that, the frame rates are taken with high eyecandy - the lower cards could do ok if the resolution and settings wre turned down a bit.
Note the severe, SEVERE drop on Radeon "SE" models - a 9600Pro is more powerful than a 9800SE.
In the Radeon models, "SE" is down a LOT, PRO is up a bit, XT is up a bit more.
In the Nvidia models, XT is down, and Ultra is up - remember which way those prefixes run, and maybe print that performance chart, and it'll help you judge what's hot and what's not.
If you want to play at 1024x768 resolution, with maximum visual quality, then I wouldn't go below the "straight" Radeon 9800 on that chart.
If you turn the wick down a bit (800x600), then maybe the Radeon 9600XT or the Geforce 5700 Ultra would be a fair target "performance-value".
If you really cut the pretty-pretty filtering down, or go to 640x480, then The 9800SE (note just how far down it is on the 9800), 9600Pro, or Geforce 5700 non-Ultra may do.
If they reckon it would run at all on a 32Mb/T&L card - like my Geforce 2 MX, then it must be with 90% of the graphics features turned off!
I suppose the other question is - do you have the processor speed to do justice to a high-end video card, though with the amount ow work done by the card, they aren't usually processor limited unless the base system is really feeble.