Text Adventures/Point and Click Adventures
When games appeared on computers they took the form of text adventures. Programmatic inputs were necessary to interact with the world. And for the most part, players had a very strong connection with the narrative and story. Even to the point where they cried.
However, once these types of games became graphical like the Sierra Adventure games, a level of connection was severed slightly. While the input was the same, the output wasn't fuel for the players imagination. What could have been an epic was reduced to cartoon or comic style graphics.
It's similar to the experience of watching Lord of the Rings animated and reading the novels. The iconic almost comical style of the animation somewhat lessens the experience of the story. However, with more realism and cinematic styling as the live action films, the connection is restored and perhaps even enhanced by the visuals and audio.
Games have not yet achieved this realism nor do they always employ cinematic communication that has become so effective in film.
Role Play Game/Platformers
Moving on, one of the most story driven genres of games is RPGs and Action Adventure games. Role Play Games generally have the same game mechanics with minor variations here and there. So the draw of the game is not usually the mechanics of random battles and such. Characters and a plot to engage the player allows for that extra draw. It is what gives the game purpose. Platformers are like this too.
Especially for single player games a reason as to "why" the player is playing becomes tied with their involvement with it.
With the current generation of games available, narratives are everywhere although many retread tired ground. Nearly ever game genre has a story-mode to go through. Things are slowly becoming as diverse as films. There are horror stories, fantasy, sci-fi, war, melodrama, westerns, mythology, folklore (not the game the stories) and even historical.
So have games become like literature in a sense? A visual means to tell a story?
There is a genre of "games" called visual novels that are just that. On screen characters and dialog that can be clicked through. Some of which are full of branching dialog. They are slowly becoming more prevalent in games but not in a Japanese Dating Game style...well...actually they sort of are. Currently, Western Visual Novels are broken up by exploration and battle systems between story cinematics. Games like Neverwinter Nights 2, Mass Effect and their ilk have a massive branching story that both validates player's actions and shapes the environment.
But then there are games like Heavy Rain which are like interactive movies.
Sandboxes, Legos, and Roads
It's all about how much control you put into the player's hands as far as the story goes.
In a sandbox game, the player defines the world however they like and tells their own story. (By sandbox games I do not mean games like GTA4 or Red Dead Redemption. I'm talking about games that can be full modded like the Sims or NWN2 toolset).
Other games give players tools to customize their story playing experience such as character customizing, choice systems and other world changing options. (This is what I think of with GTA4 and their ilk.)
And there are games that limit the player to one character and one storyline.
In other words, in sandboxes the player is the author, Lego games the player is co-author, and on road games the game developer is the author.
Appealing to a Wider Audience
The greatest difference between movies and games is their general appeal and accessibility.
Most people can handle sitting down and watching a movie. Not everyone can pick up a controller as easily.
Then there is the appeal of game stories vs film. In general, a war story only appeals to a limited audience. While I personally enjoy films like Gettysburg, I'm not particularly interested in films like the Hunt for Red October or Patton.
There are many well made and well loved war films and stories, but not so for games. They appeal to a niche.
Same with things like high fantasy, comic super heroes, and sci-fi. These are all niche audiences. Sure you CAN make stories from these genres appeal to a general audience. That is what film has been doing very well in the last decade or so. They have rebooted high fantasy tolerance with films like The Lord of the Rings, Chronicles of Narnia, and their ilk. Comics with X-men, Iron Man, and Batman. And even sci-fi with the new Star Trek movie and Avatar.
Part of the appeal is that the audience doesn't control the story. It's told to them. But also elements like using specific actors, highlighting elements that appeal to many audiences (humor, romance, action) and balancing them accordingly.
I think video games stories should take a hint from Hollywood. They know how to make a story fit with a general audience. However, at the same time there are many very under appreciated games that tell wonderful stories that are either only small releases that no one hears about or advertising shot in the foot or they're just old.
With the multiple ways a narrative can be presented, I think games have untapped potential for delivering a truly emotional experience.