Starcraft is by its nature a 256-color game. When played full screen, the display is set to 256 colors. When played in a window on a screen set to thousands or millions, there are still only 256 colors used, the OS takes care of translating the 256-color imagery onto the deeper screen. Full screen mode is faster because of this extra step that can be skipped.
It's also only a 640x480 resolution game.
Rob