Traditionally game story telling usually uses a film model of storytelling - there is one big overwhelming foe to fight, and the player's character (or characters) develop until such time as the can challenge foe is a suitably dramatic location.
The recent project I was on (that just got canned) was a fairly traditional 3rd person action game. Now, when development started there was an assumption right from the start that we'd just be using the same old method of storytelling: here's all the cutscenes laid out at the beginning, let's just string some gameplay together to link them up.There has to be something better than that.
Id like to see more games move to something more akin to the television model used in series like those produced by Joss Whedon. What frequently happens in his series is that each season there will be a group of episodes at the beginning that just establish characters. Foreshadowing of the future BBEG (Big Bad Evil Guy) starts to take place with the main characters encountering minions performing tasks that will be part of the overall plan, until the BBEG is revealed.
The BBEG wins a few battles to unsettle our heroes/heroines (now that's a revolutionary concept in games, and I know - it's hard to pull off without disenfranchising the player) until the heroes come to the climactic battle.
But in between the main story arc episodes there are numerous 'filler' episodes that take the characters away from this plot and break it up.
New locations are added every season to the basic group of sets that have been built for the show, increasing the variety of locations that can be used.
I think this could serve as a much better model for episodic content, with player's downloading the equivalent of a season, rather than an episode. It would contain a new BBEG for the player to fight, a new set of 'filler' episodes that could be thrown around (ideally in a random order, but I've got more details of that system to come), and slowly add new locations, while still keeping the story around those used previously.