I've always been a huge fan of the C&C series. In fact, C&C 1 was my very first pc game when it first came out and I gotta say, that game is magical. Truly magical. I mean, wow. Where the other games are about building a lot of resource gatherers and sending out a huge army, this one is about micromanagement, strategic and tactical considerations and financial management, even. And I absolutely loved the storyline.
Red Alert 2 is a lot of fun, especially yuri's revenge expansion, but it's so different from the classic C&C 1 and Red Alert 1 that it lacks the
magic. (it's such a great game, though, that it sort of has its own magic)
Tiberian sun was sort of a let down (extremely hyped) but still really great - and you will probably crave for this after C&C1 because they are the same story (C&C1 is aka "Tiberian Dawn")
I also had a lot of fun with Generals, but, again, no magic whatsoever. Plus it's a bit more graphics intensive.
I say start with C&C1 and work your way up