I contribute to an Escape Velocity-derived game on GitHub by writing and reviewing missions and stories. While the official guideline is that you shouldn't be writing like a novel, a lot of the game is text-based story. Certainly I've heard praise for the game's stories, and also some pretty visceral reactions to what is just a text-based game with some flying and shooting in 2D space.
People are divided on whether the game is story-based or mechanic-based. Obviously I say it is story-based, but the problem is that many people playing the game fundamentally do not care about the story and look for better rewards (basically, larger numbers and better spaceships); they're more than willing to spoil themselves in order to get "the better ending". That makes me sad, because I contribute to the game for people to read quality stories, not for them to be skipped for rewards.
There is another dichotomy between FPS games like Doom and Marathon. Marathon has a brilliant and deep story, but Doom is considered to be a better FPS game (that as far as I can tell has a story that makes little sense). Similarly to the previous game, much of Marathon's story is told through text based terminals. Today Doom's popularity outstrips Marathon, but that might change as interest in Marathon's story is resurfacing.
In my opinion, the best games tell their stories through the game's mechanics. For a board game example (I know it's not the subject, but it could be helpful), Oath could be considered quite good at this because it relies on the cards players utilise to create the story of the game. There is no "lore"; players interpret what the cards represent based on the context. In my last game, I (an Exile vying for the Chancellorship) hid out in the River Valley mustering troops, leveraging A Small Favor from the people there to rapidly enlarge my forces. Then, I defeated the bandits to become the ruler of the Deep Woods. With their support, the inhabitants of the Woods and their Martial Culture led me to gain citizenship of the Empire, when I proved my worth in battle by defeating the holder of the Grand Sceptor decisively at the Tribunal (the defender rolled 0 defence, amazingly. My advisors must have used Encirclement in battle very effectively). Since the existing Chancellor's oath was fulfiled, I was his successor when I took hold of the Sceptor, leading me to victory when his tenure of the Empire was over. Oath has no story, it's just whatever you make up in your head that the board facilitates. It does take like 3 hours, though. So, it's similar to Civilization where you can create the story through the mechanics of the game. (Interestingly, the designer of Oath called the game his "hate letter" to civilization boardgames.)
. But it's fixable. Park Ranger comes out with new games once or twice a year, and I can plot faster than that. Ranger Betty can go take a hike (pun totally intended)! 
