WC3
Well, WC4 had quite the interesting 'conspiracy' plot, which made it REALLY unpredictable. I couldn't put it down, but...
WC3 was really my Favorite. It was a shock to see our pixellated blue-haired friend and the ol' cast appear as real actors. The acting was also pretty good for a computer game (look at the lame acting in Red Alert 2) and gave you the 'epic' story look. Imagine:
You were caught in an unending war. A super-weapon, destroyed by a traitorous friend. Your love, killed by an evil adversary. And, yet hope. One shot, you must fly to the enemy homeworld, an impenetrable base, with a lone fighter and destroy it to save all humanity, mere hours before the invasion of earth would begin!
WC2 was my second though, because it introduced a LOT of concepts, like bombers, torpies, a real good plot, traitors, turrets, Phase shields, Jump missions, *love*, intrigue, cutscenes, plot twists, and all kinds of other revolutionary things.