Making 2-player Starcraft more enjoyable
The Brood War expansion includes a number of scenarios, one of which is explicitly designed for two players.  The gameplay in a scenario is pretty much the same as the core game, except with predetermined galaxy layout and often some form of "capture the objective"-style mechanic added (the two-player scenario, for example, prevents either side from moving onto the Terran's home planet unless they have control of a "bridge" zone first).  I don't have the rulebook handy for reference so I don't know if the two-player scenario is entirely playable with only base-set pieces.

Fantasy Flight Games offers this scenario for free download, which is for four players (two teams of two players); there's no reason it can't be played with two players each playing both factions of a team.  It does however require pieces from the expansion.