Starcraft is 2D, so it doesn't matter how fast your video card is at 3D. Just get the cheapest card you can find with good signal quality (crisp, not blurry, text). Try for a Radeon 7500 or GF4MX440 or FX5200, just make sure you're getting a 128-bit memory bus.
If the cheapest cards you can find new are about $50, then you'll get much better value buying used from a good trader in Anandtech.
If the cheapest cards you can find new are about $50, then you'll get much better value buying used from a good trader in Anandtech.