Take stock of these three factors:
CPU - Maybe a 3GHz or higher processor: (Assuming its a skt478)
RAM - 2 x 1GB PC3200
GPU - Check out the 6600 AGP series cards from Nvidia:
There are 7600 series cards but then it means more $:
Your RAM @ 2 x 512Mb is pretty much the minimum a gaming PC should have.
You could try to OC your processor, unless you have an OEM PC. OEM PC's are much harder (if at all) to get a decent OC boost.
I realize that you don't have the $ for a PCI-E MoBo. That is a form-factor you should consider updating in the next 12 months as AGP has reached "end of life".
Hope that this helps.