A very good example would be Mass Effect, particularly the second game. Very tight gameplay mechanics IMHO (well, except maybe the mining stuff) and a super strong story with great characters and nice pacing. I think the way the game calculated the ending (basically the casualties from your team) was very well done too, rewarding not just a methodical approach but also your knowledge of the team members (assigning the right characters for each job). You could've gotten away with saving everyone or you could've got everyone killed including Shepard...
Other games I'd list for having a good balance would be System Shock 2, Deus Ex and probably Ultima VII part 2: The Serpent Isle. Except for SI, they had some very complex game mechanics and lots of emergent gameplay, and yet they were massively story driven and also offered player choices with more or less significant results; even though those weren't really about the story but about how you were able to approach the various gameplay challenges.
SI on the other hand was actually very linear, both in the story and the gameplay (maxing out the Avatar was a one-way street) - but the narrative was just super strong and the game was actually quite hard. I mean they went there and hid a key in an INVISIBLE chest at one point
Also, Ultima VII: The Black Gate was different in that the story was driven by the locations and after leaving the first town you were allowed to visit the rest of Britannia in any order; and the plot was driven by detective work, uncovering clues and so on. And both games had an open world that I believe is still unique - NPCs with schedules and the ability to bake bread from crops you've harvested... I haven't played any Elder Scrolls games since the first one (which I've quit in the first randomized dungeon...) but I don't think those were as complex as Origin's twin masterpieces.
I could also add the two Ultima Underworld games here, but I think that maybe the narratives weren't as strong in those. I've still spent a LOT of time with them all those years ago and enjoyed the hell out of it
Thinking about it a bit more, I'd also add Outcast - the game reminded me a LOT of the Ultimas at its time, with the action and exploration and puzzles/quests and conversation aspects all covered, although in a TPS implementation and without the character stats progression.
So my point is that it should be completely possible to create video games that have them both, complex gameplay and strong narrative. The problem seems to be that the expected complexity of the various systems is just far too high and corners have to be cut here and there. Also, and perhaps more importantly, the games with large enough budgets to implement all this stuff at today's quality levels have to be far more simple to sell enough copies; for example, I think an Ultima VII type game should be quite possible on the GTA engine - but adding conversations and puzzles and such would just alienate most of the customers...