I'd go for the HD 4650. I would never buy anything lower than a GTS 240 from nvidia. The 4650 is outdated, but it still handles several games pretty well. Just stay away from Crysis and Bad Company 2, unless you have a kick-ass CPU.
You should deff get something like a 4850 then. It would be a decent compliment to the Phenom x4 you've got there.
Or a GTS 250, or 9800GTX+, or an HD5750, or even higher. But as mentioned, it depends on your budget. What's your max you're willing to pay for?
Yeah, I remember when I was using an HD 4850 by XFX for about a month, and I was running it on a 380W PSU without any lack-of-power issues.
Btw, a lot of people always say "Just go with a good brand" when it comes to buying a PSU, but that's just a rule of thumb if you don't know what you're looking for. If it's a card that needs only a moderate amount of power (like the 4850), I'm pretty sure you can buy a cheaper brand and save you're self some money. Just look for a PSU that's 500W and has 20A each on a dual +12V rail. Be sure to look at customer reviews, too. : D
Then again, if you find a really good sale on a brand name PSU, go for it.
cheap PSUs can fail, and take half a system with them. its not a general rule, its something that everyone here preaches incessantly for good reason. a PSU is the one place where you absolutely must not skimp. get a cheap brand to save a few backs, and it will die years sooner, and has a chance of taking another component (or multiple) with it.
a good PSU will last longer, be efficient and cool and is not going to go jihad on your motherboard.