The type of Power Supply you can use is based on your case more than anything else. If it is a standard ATX power supply in there now, you can upgrade to pretty much anything on the market. Some vendors have custom PSU shapes, hole placement in the case, etc... that make it hard to upgrade a PSU, you need to get some info on your computer model and vendor, look at the power supply and see it it is shaped the same as others online.
As hunter said, if you have an AGP slot, you will be hard pressed to find a good video card now, new, or expect fast game play.