I could totally do it for $500 but not brand new. I'd have to look for used parts on kijiji, forums, ebay, etc. I build a computer like this for a friend. He runs SC2 on medium-high settings.
$80 motherboard
$75 8800 GT 512MB
$120 Core2Duo 775 CPU
$90 4GB RAM
$50 400-450W PSU
$55 Case
$30 Miscellaneous Parts
----
$500 totally reasonable
You'd never find something like that in a store though. You'd have to bargain hunt for used parts and get someone to build it for you. No labor or software included.
The other option is to hack a PC graphics card into your laptop but that might be a little advanced for you. :P
http://hardforum.com/showthread.php?t=1522180