boils down to -> do this, this and this in exactly this order, under certain amount of time and you will win.Exactly, I'm not some korean robot that does that full-time, so I will never play it perfectly.
Some games try to rock, paper, scissor, where every unit has some counter unit, but ultimatly it means there won't be many surprises.
On the other hand if you put in too much randomness it's no longer a strategy game...
I guess it's because most games try to serve to competetive players. When I was younger and Internet wasn't something everybody had I played mostly with friends. I've got the feeling the games where more interesting and we experimented much more.
Nowadays it's all about playing regulary and climbing up the ladder. I don't have time or motivation to play every day/week/month just to stay good at a game. Besides most games just don't have enough content to keep me interested for such a long time. I mean after playing the campaing and maybe a dozen games in multiplayer you've seen everything there is to discover in SC2. Now one only needs to repeat until his hands are bleeding and he is a so-called pro.
Make a game that's fun too play and that a good player can win even if he/she paused for a few month. Make it different each time (maybe radomize the map) so it won't be possible to use some standard strategy found on the internet. Don't make it a race, where you just have to be faster than everybody else to win.
To me chess is the ultimate strategy game. No randomnes and complete view of the board, only the things in your opponents head are a secret (you can still try to guess).
And because there are also standard openings and opening books, some people suggested to place the pieces more or less randomly and then play, after a winner is found put the pieces back, just like the first time but switch sides. That way the board doesn't have to be fair, balanced or symmetric, you don't even have to place the same number of pieces for each color.
You could also take a look at bridge (the card game) as far as I know they are also reusing the same random hand of cards and switch them between SN and EW too keep it fair.
Edit: You could even randomize the available technologies each time to prevent boring standard tactics.
Easy: Don't allow Infantery unit X Hard: No flying units this round.