adding continuity / storyline in games

hello everyone:

i have a general topic i'd like to ask everyone's opinion/experiences/ideas/wish list on:

what "devices" can you use to add continuity to a game? for example, in Civilization you have time (going from stone age to modern era) and also building this-or-that (continuous upgrades) and two devices that add continuity to the game, a sort of story line...so that you're not "just doing the same thing over and over"...even though you are doing the same thing over and over; but the passage of time (striving to get to an era first) and the need to upgrade...make it feel like you're not doing the same thing over and over.

what other devices have you experiences, would love to see but have not in games that gives it a continuous story line...a feeling of progression/striving for something other that "just" doing the same thing over.

i'm about 60% done with a cross-genre FPS and would like to make it more than just a "gun and run" by giving it a sense of evolution, a sense of milestones that you strive for. and i'm stuck.

any ideas would be greatly appreciated.

Competitive game with a ranking in place. Done.

Actually I think if you keep the game mechanics interesting like giving different approaches to solve a problem (in Civilization this for example would be enabling the players to emphasize on different technologies to play out different advantages each game, also different innate boni, ...), it won't feel like doing the same thing over and over at least not fast. FPS is a problem though, I think the gameplay in those is mostly boring if we are not talking about competitive titles and they are carried by their storiees and some short-lived action-movie-esque fun. The best single player approaches (for me) are probably those that let you play through the campain without killing a single unit.

The best example of neverending possiblities so far has been DotA/Dota 2 for me. Game keeps staying fresh for me for 7 years now, ofc continuous patches help as well.