Good examples folks. Personally, my favorite set-piece story would have to be the one in Mass Effect. By Mass Effect I mean the first one, mind you. Not ME2 (which was actually rather good, but took a weird sidetrack), nor ME3 (which wasn’t as terrible as it was made out to be, but ended badly), nor The Other One That Shall Not Be Named (which just made my “face tired” from laughing at how awful its story actually is). I really enjoyed ME1, and will even play it periodically to this day. Of course, as I’ve mentioned before, it’s story is basically a modified version of that in my all-time favorite video game Star Control II (picture the Reapers, but they never leave the galaxy and have two warring factions: one that wants to kill everything versus one that wants to imprison everything; plus a MUCH bigger catalog of star systems and races). But ME1 has it all over SC2 by looking much better, being much more polished, and by being way more accessible. Plus it doesn’t require the same time investment in order to wring every last drop of story out of it.
As for games that caused me to make up my own story in my head as it went along, my favorite was and still is the original Panzer General by SSi. Yet another game I have waxed poetic about previously, the hex & counter simplicity of its presentation demands a bit of imagination to “flesh it out” in one’s mind. The installments presented by the game were mostly predetermined by our actual historical timeline, but the actions within each contest were made up by me (and quite vividly too) in the “old noggin”.