Socket 939 AMD is probably your best bet, something in the region 3200+ to 3500+ is plenty if youre not a 'hardcore' gamer.
Although, if you dont have a PCIe graphics card, the right power supply, motherboard etc then it means a whole new PC built. What do you have at the moment?