An idea I recently stumbled across, due in part by replaying the Bloodmoon expansion to Morrowind, is the concept of the characters being payed or coerced into joining an expedition to colonize a "New World". They would travel in whatever form of transport neccesary, sailing ship, steamship, tanker, spaceship, what have you, and then be in charge of the defense and scouting of the area around wherever this new colony is to be built.
I mainly thought of this as being used as a twist for a campaign that may be falling stagnant. The characters are bored with slaying dragons or shooting orks or whatever, so they get talked into this expedition to somewhere they've never been before. They'll be facing all new challenges. Towns and such won't exist beyond the new colony, and that will take a while to be built up enough that they can rely on it for supplies. There won't be political intrigue, but there may be "savages" for them to run into and react to. All new flora and fauna to contend with. Much of it may be similar to what they're used to: "Hey, this bush has small berries with the same smell, texture and make-up of those blueberries back home, except they're purple. Maybe we can eat them!", or: "Hey, that four-legged white animal looks a lot like our grizzley bears. Maybe we should leave it alone." But some could be radically different. This is where the DM can really get creative and invent their own creatures, or find a different style of creatures for the campaign.
Keep in mind that this may annoy players as well. If they suddenly move to a new planet, a number of their skills in things like wilderness survival or plant and animal lore will no longer apply. They will be in a new environment which they have no prior knowledge of. This could definately revitalize a slowing game, but it can also form resentment if your party mage put all his skill points into geography and creature lore. Just be careful, and maybe come up with an alternative way of dealing with it so that their skills aren't totally wasted. Allow the skills to let him make intuitive, educated guesses about similar things or some such. Anyway, that's what I've got for now. Feel free to add on or comment.