The 7600GT needs only 30W or so. A 500W PSU should do very nicely, maybe even 400W. It's pointless to buy something much bigger because that PC won't allow many future upgrades. Just mind the physical size, of course.
BTW, if you can afford a 7900GS instead that would help, it's 30% faster and needs 40W.
This page gives the specs for your PC.
http://support.gateway.com/s/PC/R/5891/5891sp3.shtml
Make sure you get the PCI_E version of the 7600GT, not AGP.
Make sure you get the DDR3 version of the 7600GT, not the DDR2. The DDR2 version is much slower.
60 C is bad, but still acceptable, IMO. My Q6600 idles at 35, for example. Sure, if you add a cooler and a fan it will help.
About the PSU:
http://forum.pcmech.com/showthread.php?referrerid=33495&t=183239
Your current PSU looks like this, according to that guy:
Dimensions (L × W × H) 5.5 × 5.9 × 3.4 inches (140 × 150 × 86 × mm)
The Antec 430W has the same dimensions, except it's 6.1" in depth (i.e. length) instead of 5.5". I bet it would fit.
My Dad's HP had about 2" available on the length - I only needed to match the W and H exactly. You could also look at FSP models, excellent brand with some inexpensive models under 500W.
Here's a page about the Antec. I'm not saying buy from those guys, I only attach it because it has the dimensions. Shop around for best price.
http://iomega.axiontech.com/prdt.php?item=78393&PRICECOMPARISONSID=def209945910406c759d1604595de7f3