IMHO, what you want is a used GTX 460. Nvidia GPUs do better in SC2 and the GTX 460 1GB is pretty cheap. If you know you won't be upgrading past 1920x1200 anytime soon, or if you game at 1680x1050, then a GTX 460 768MB is almost as fast and is also plenty for SC2.
http://www.techspot.com/review/305-starcraft2-performance/page7.html (This is for 19x12 so if you are at 1920x1080 you should get slightly better performance than these numbers)
If you are okay with literally scraping by at 30 fps then you can opt for other cards. In fact, if you are truly cheap, you could probably get something like a GTS 250 or 9800 GT and overclock by 10-20% and still hit that 30fps threshold on Ultra graphics settings. Turn down graphics slightly if you must. If you are okay with playing on High instead of Ultra, even a stock 9600 GT or GT 240 GDDR5 should be okay:
http://www.techspot.com/review/305-starcraft2-performance/page8.html
And if you are okay with playing on Medium, you can go really, really cheap and the game will still look pretty good:
http://www.techspot.com/review/305-starcraft2-performance/page9.html
The problem with going that cheap is that your bang for the buck doesn't get better and might even get worse if you start scraping the bottom of the barrel. I mean yeah you could buy a GT 240 512GB GDDR5 and overclock it and do fine, but for many modern games,you would have to play on Medium or lower, and the card will still cost you what, $30-40 used? If you were to pay an additional $30, you could get a used GTX 460 1GB that would be a viable gaming card for much longer (thanks to faster GPU and more VRAM) and let you play on High/Ultra in most games, and most GTX 460's can overclock some crazy amount even at stock voltage.. you could get 800MHz on stock easily.
Now you may say: but I am playing SC2 exclusively! But even so, you may run into situations even more extreme than what they tested for in Techspot, like if you have a mothership cloaking a bunch of units and are fighting another guy who also has a mothership cloaking a bunch of units, each of you with observers sort of in range. That's a CPU and GPU-straining fight and you really don't want to be lagged too badly there. Also, 4v4s can get really intense too. And Legacy of the Void may require higher graphics in a couple of years. I don't know.. I just think $30-40 for a low end card isn't good bang for the buck and you should at the bare minimum get a used GT 9800 or GTS 250 for, say, $40-50 to get a smoother experience and more bang for the buck.[/QUOTE
I am playing with an i5 and a hd7770, single player. I get around 4O fps on ultra. Surprisingly I am gpu bound in this scenario. You could get a used card as this poster suggested, but unless you can get one from someone who you know is reliable, I would try to get enough extra to just get a new hd7770 or 7750. I got mine for 90.00 after rebate on sale at microcenter. That is only 40 or 50 dollars more than a used card, you know it hasn't been abused, and you have a warranty.