I mean just think of some of the cool story beats and cosmetic touches in Starcraft - the awesome little black comedy with Lester and the zergling; the smart little bit that plays on Mengsk as a rebel against a nasty Confederacy, and then it turns out he's a cynical little tyrant himself; the speech Mengsk gives when he comes into power; the injured Dragoon bit. There's quite a lot of memorable stuff there.
And Brood War is even better, despite some plot holes. I really think Brood War is a fantastic story, probably the best of any of the many RTS I've played (yes, even Homeworld). The way the stodgy and dogmatic Aldaris turns out to be surprisingly prescient, while all the more open-minded characters have the wool pulled over their eyes, and get played by Kerrigan. The way Kerrigan's hold over Razhagal is left somewhat open-ended and unresolved, and not ruined by ham-fisted over-exposition. Stukov v. Dugalle is a great conflict- even if the UED themselves are kinda out of place, and are treated more as a plot device than as a real faction. Fenix's death is brilliant. Kerrigan is appropriately smart and manipulative. The ending is rather bleak and, even for the victorious Kerrigan, decidedly downbeat.
Or just think of Raynor's original character design. A fairly young balding man with a pencil moustache. Whereas the new 'rugged' Raynor design is a great symbol of everything that's kind of stupid about Starcraft 2's story.