What would you guys think if there was a more story based strategy game? Maybe a little more restricted in terms of choice but with more story options.
It depends.
To me, the idea of a 'story based game' is a bit of an oxymoron. A game may have a background story that provides some context and theme for a game, but if you try to shoehorn a linear concept such as a pre-written story into medium which is fundamentally non-linear, something is going to suffer.
Sometimes it's the story - the author is forced to try and think of every eventuality, and/or accept the fact that sometimes things will happen that don't make a whole lot of sense. In either case, the effort involved in writing the story balloons as you try and cover all the possible branches, often with the result that overall quality suffers.
Sometimes it's the game. In order to retain the sense of the story, the player is forced onto rails, with limited choice. The player can't even fail - there's no 'win' or 'lose', its more 'finish the story' or 'don't finish the story', usually with boredom or frustration being the cause of the latter. Or perhaps the game is interspersed with an excess of non-game fluffery, long text sequences or cutscenes with no TL:DR option. And once I've sat through the whole thing, what motivation is there to play it again?
Often, it's both, to some degree.
On the other hand, all games have a story - the meta-story the player experiences during his own path through the game. This to me is a far more dynamic and interesting area to explore than a fixed, handwritten plot. If you can establish engaging lore and backstory, and provide the players with the gameplay tools to do so, they will tell their own stories. And those stories will be unique for every player, on every playthrough.
So to answer your question: If you can make an engaging'meta-story' experience, I will definitely play it and enjoy it. Otherwise, I might have a quick play of your story based campaign, but the chances are, unless you can avoid committing any of the Strategy Game Story Deadly Sins, I probably won't finish it, and head off to multiplayer/skirmish instead.
I think you are right so far as you can't really have it both ways - you can't have an interactive story where the player has complete freedom to do whatever, and think you can have a cohesive, unified, engaging narrative. But I think you are wrong when you say that games are fundamentally non-linear. Most games have one beginning, one ending/conclusion and progress in a linear fashion from the beginning to the end (with bubbles of freedom of action along the way).
I believe the reason story and games don't seem to mix well is because of 1. bad writing (such as too much exposition, back-story and red herrings), 2. trying to incorporate branching story-lines and multiple endings (mass effect 3 anyone?), 3. story is an after-thought slapped upon the game-play.