The Role of Story in Games

I would say that there are 4 levels of story in games, and how they relate to the gameplay.

0% Story Level - Sandbox Gameplay
In this type of game, there is no story, and you play the game for what it is: a game. Some people say in this type of game "you create your own story," but that's just kind of dumb. There are no stories in these games, there is just gameplay. That is fine, and especially fine if the gameplay is so addictive and amazing that a story will just detract from it.
THINK OF: Jetpack, Sammy-Snake, Tetris, Pac-Man, Roller Coaster Tycoon, Transport Tycoon, Theme Hospital, or any Tycoon game.

10-20% Story Level - Guide To Your Actions
In this level, the gameplay is executed similarily as before, except there is a small driving force for your actions. You are given a huge sandbox to play in, but you have a reason to play in it other than "WIN." You know why you're there, what your motives are, and what you're trying to achieve. These type of games may only progress the story in cut-scenes in between missions and such.
THINK OF: Millennium: Return to Earth, Command & Conquer, Warcraft, Heroes of Might & Magic, or any other strategy game.

50% Story Level - Tour Guide
In this style of gameplay, there is a delicate balance between story and freedom. At the beginning of the game, you are given a clear goal, the direction to achieve it, but it is your choice when and if you achieve it. You may be limited on that path, but you will have plenty of freedom to explore the area along that path.
THINK OF: Final Fantasy, Quest For Glory, KotOR, Monkey Island, or any other adventure/RPG game.

100% Story Level - No Freedom
The final and most restrictive style of story on the gameplay; this style is mainly used for cinematic games. Everything you do in this game is a direct result from the story. There are no side-quests or extra things to do other than progress the story by your actiosn. Any deviation from the main story or executing side-tasks will probably detract from the atmosphere in this story. The developers must choose to restrict the player on the single path the designers have chosen, because if the player wanders off, the result will be a loss of immersion.
THINK OF: Half-Life, Halo, Call of Duty, other FPSs, and some adventure games probably.

Based on the above, it would seem that strategy games have the least amount of story. First Person shooters on the other hand restrict you directly to the story. And somewhere stuck in the middle are role-playing games which have a main story, but let you do whatever you want. Adventure games can be fully about the story, or have some deviation.

You could probably list those old console games like Mario, Donkey Kong, and Sonic somewhere along these lines, but it would be awkward. Those games restrict you to one path, but don't have a strong story. They would be listed in the 10-20% category, yet there is no freedom.