Are you familiar with King of Dragon Pass? It's, to my mind, the archetypical story/strategy game.
The strategy is around establishing a mythical/fantasy tribe in a new land, and the story comes in as you have to manage people as individuals as well as the tribe as a whole.
I'm glad someone mentioned this. KoDP has a great story.
I am working on my modified RTS engine right now trying to make weird genre blending exploratory strategy games. Currently I'm doing Majesty/Emperor combo but with deeper guilds, but later I'm going to be doing some storyish Dominions/KoDP event system style things. I'm actually writing the event code right now. There are gonna be several individual events but also some long interlocked series of events.
If OP ends up making a game I'll be interested to see his method of integrating story. I'm always looking for new surprising genre combos.