The Total War series, Shogun being my most fondly remembered (Ninja assassination videos!),
Starcraft (loved that game, the sequel had better live up to the name),
Dawn of War and Company of Heroes. I mention both because they have very similar gameplay. I didn't think I would like the 'Strategic Points' idea in an RTS but DoW proved me wrong and CoH put the system in a setting I prefer, not being overly interested in the Warhammer universes,
and last but not least: Total Annihilation. I remember thinking when first building a Nuke it would be like a 'Red alert' nuke, you know, like kill some men whilst barely scratching most buildings. When I finally used it all I could say was 'Whoa'.