A quick Google search says the cpu in your Gateway GT5628 is a Q6600 and that you have a 400 watt psu, you'll need to open the case and find the label on the power supply in order to find the 12v amps.
If not, I'll have to crack this bad boy open I guess. >.>
Somewhat, the link to the Delta shows a combined output of upto 30 amps on the 12v rails, that being the case you wouldn't really need a power supply upgrade for either of the cards that have been reccomended.
newegg has this today.............providing the mobo can support it.
I have the MSI card and one thing to consider is airflow in your case. I was looking at your case on the Gateway site and I didn't see any fans pushing air in or pulling air out of the case other than the power supply. You may want to consider getting a fan for the rear vent if it doesn't already have one. And you will need a 4 pin Molex (from PSU) to 6 pin adapter for the graphics card. I don't remember if the MSI came with the adapter in the box. I'm at work so I can't check it until I get home.
If I don't need an upgrade for my power and if it'll fit, I guess I'll go with the Radeon HD 4850. I'll also get a fan, and wait until we know about the adapter before I finalize...