I can't believe nobody has mentioned XCOM: Enemy Unknown yet. Most of the missions are randomly generated "enemies on a map" with a few scripted Council/Terror missions thrown in.
What takes place IN those missions as your small squads are relentlessly whittled down by alien forces acting without (at first) any human-discernable rhyme or reason is basically...
...any episode of any of the "Stargate" TV franchises.
Aside from a splash of color or something on the uniforms, I never mess with the pregenerated names or appearances of my squaddies. As a result, I am often treated to anxiety-riddled gun battles and heartbreaking acts of self-sacrifice and battlefield heroism as my veterans face off against enemies that have them both outmanned and outgunned.
Research and manufacturing decisions affect the gear carried into battles and the agregate success of missions determines the course of mankind's war with the alien threat.
The overall "game" though is just a scripted collection of milestones in the course of the same war. Even though the war could play out very differently the next time, there are still going to be the same cutscenes and the same main story points.
If there could be some way to "shuffle" the aliens' motives, methods, milestones or "endgame" so that you could never be entirely sure what the aliens were after or what actions would advance the story (or in what direction the story will take based on your actions) then you'd have a constantly varying "series" arc as well from game to game.