nVIDIA GPU. Fast "OC" version of GTS-250 with 1Gb VRAM would perform faster than 550 Ti. Any GTX-270 card with wide memory bus width would also be faster. nVIDIA cards from 4xx/5xx series are great if you care about GPU compuiting power, tessellation and alike, but are slower than previous generations when it comes to traditional renderpaths from DirectX 9 and OpenGL2.x world.
P.S. And make sure you head with nVIDIA way - cards from AMD are good but drivers are still not so stables as nVIDIA's are.
P.P.S. Also be sure to use fresh enough version of Wine, at least 1.3.28, as there were a lot of changes in d3d emulation that boosted FPS a lot. Note, that you still won't be able to set highest quality settings in SC2 due to some render bugs showing up when shaders quality is set to be anything higher than "medium". To display in-game FPS counter use Ctrl+Alt+F combo (or Ctrl+Shift+F, or Ctrl+Alt+Shift+F - don't remember which is it exactly).