Arguably, this is simply shorthand, much as genre names are. In the same way that we would describe Team Fortress 2 as an FPS, or Fable II as an RPG, these three categories are a way of asking: What does the player want? What draws the player in?
Is it discovering the past, understanding the present, or shaping the future? What experience do you want your player to have? And, most importantly, how can you make it more personal?
Never forget that we, when playing games, are somewhat selfish creatures. We want the game world to be about us, and we want it to grab us within those first vital minutes and convince us that this game, not that one, is what we need right now. This is where games need to develop their own 10 minute rule, though the "10" is negotiable.
Depending on the length of the game, the introductory hook could come anywhere from one minute to three hours in. But never forget, you do need to hook your player. How quickly you do so is reliant on the gameplay.
The pace of a Story is faster than that of a History, while a Mystery is faster still. Do you want your player to be thrown into your world with a bang, or are they going to spend most of their time exploring? What is the pace of an intended playthrough?
That's a good start.
So here, then, are a few questions to get you started on thinking about where the story should start for your player. The old adage from film -- to get in as close to the action as possible and jump out as soon as it's over -- definitely still has a hand in choosing where to begin, but the how is something you need to know even before that.
That last question is one I would urge every developer to consider. It's far better to leave your audience wishing the story segments were longer than to overload them with information they don't care about or understand.
Like, well, any of the Twilight series.
So what does this mean for you, in the long run? Stick to the good old storytelling rules -- the best stories combine inevitability with irony, show don't tell, sometimes the best answer is silence -- but think about how you're delivering that narrative, too. Does it mesh with the player's in-game experience? Does a slow story building to a dramatic finale really suit your hardcore FPS?
In some cases -- Halo: Reach, for example -- the answer is yes. But to be able to judge whether or not your story suits, you need to know who you're making the game for. You need to know what they like, what they love, and what they hate. You need to do research. Once you've done your research, you will know what the first 10 minutes of your game should be. You will have your hook.
Know that, and you will know your audience.
Know your audience, and they will love you for it.