What story?

I didnt really notice 1

Hm...HoMaM 4, Sacrifice, Original War, Giants, Jagged allaince or Earth 2150... tough choice :( which one of these combines great story and gameplay?

Id say Sacrifice (from others oppinions)

or

GIANTS:CK <--- Awesome

I didn't see anything about whether you prefer turn based or RTS but my vote would go for Warcraft III and Starcraft. Both games are pretty cinematic. Especially if you're able to play Starcraft II. Sure, they aren't the best story campaigns I've ever heard but they're pretty decent as far as strategy is concerned.

I like both genres, and already played WC3 + SC,SC2 :)
So hard to choose...I guess I will flip a coin :)

Whoa, i kind of liked it a lot, actually. But, since it's not the first time i've heard something like that, let's say it's an acquired taste.

Oh, and both Starcrafts are quite nice storywise. Not that i recommend them, though.

/ninja'd about Sc. Both Sacrifice and Giants are awesome, but they're not pure 'strategy'. Better find gameplay videos on, say, Youtube before making a decision.