Now, I'd like to go back to story and scope for a moment. If we want a small game to start off, a sprawling time travel epic is probably not a good choice...but let's look at sidestory possibilities. That would give us something that ties in with the eventual larger game to create something bigger than either of them alone. At the same time, it needs to be a reasonably complete story, with no more loose ends than necessary.
We could cover the history of any of the eventual characters, of course, but just for the heck of it, let's go back to the prince's friend/girlfriend Liara, lost somewhere in time. So. She lands in the far future. She has the clothes on her back, one valuable piece of jewelry, a knife, and a few magic tricks. No ID, no friends, no prospects.
She pawns her [necklace, probably] to get a bit of money. She finds out where to get fake ID, but it's a shady area of town. This gives us Dungeon #1.
Having gotten the ID, she finds out that it doesn't help her nearly as much as she expected it would—there's no educational or work history to go with it, so she can't get a job unless she wants to 1. wait tables in a dubious bar with implications of prostitution on the side, or 2. join the infantry. She opts for the infantry.
Pulling a page from the David Lynch Dune movie, let's say that fancy shielding tech has made most guns obsolete in the far future—to penetrate a shield, you need something that can keep physical pressure on it for a while, an energy source capable of overloading it (big energy drain if you want more than a few shots), or something that moves more slowly than a bullet. Also, the three-legged race between communications and disrupting same means that drones and other remote-controlled ordnance aren't very reliable most of the time. As a result, swords and spears in the hands of foot soldiers are once again favoured weapons.
There's an opportunity during the military-training segment for tutorials and/or minigames (button-mashing pushups, frex, or gambling at night in the barracks for useful items). The grunts are sent on their last training mission before graduation, and Something Goes Horribly Wrong (natural disaster, enemy attack, AT-AT-oid from the past drops out of Time and onto their heads, etc.), giving us Dungeon #2. Liara manages to distinguish herself during the scramble to get out and is recruited for Special Ops, or something of the sort.
There follow around 3-5 missions, each with a different theme (retrieve the cached information, find out what's inside the building, make sure the hostage doesn't talk—we don't care if you shoot him or rescue him, steal valuable prototype from enemy weapons facility, etc.) Liara continues to distinguish herself, and is promoted. At the same time, she has to conceal the fact that she knows magic, because that would prove she Isn't Who She Says She Is (and probably get her vivisected in the bargain). During her spare time, she can return to Dungeon #1 to level up if she wants to do so.
Her last mission has to 1. tie back into the time travel theme somehow and 2. result in her doing something really impressive against the enemy-of-the-moment of the people she's working for (I'm open to suggestions). She gets a medal for it, and a good-sized bonus. She uses the money to go back to the pawn shop from the beginning of the game and buy back her necklace. The last scene has her opening the attached locket and looking at the picture inside, which is of her and Prince What's-his-name, and reflecting on how she isn't the person in the picture anymore.
One of the bonuses of this kind of story is that it's viable to make many of the NPC designs semi-interchangeable—different heads on one military-uniformed body. Also, we could have a PC party or just Liara as sole protagonist, depending on how we want to go about things.
