Answering this depends on what kind of "story" you're looking for in a game. Most games rely on a "narrative engine" that works (usually) parallel with the core mechanics of the game. Things like context, character motivations, plot, narrative events (i.e. cutscenes), dialogue, and events of the story all come from the narrative engine. To give an example of the separate elements to each game, using Deus Ex: Human Revolution: Defining the character through the augmentations, praxis points, and choice of weaponry is part of the core mechanics; while the image of Adam Jensen, his motive, and dialogue come from the narrative engine.
I assume you are referring to games that rely on narrative engines that tell a story (there are games that tell a story through core mechanics and is a bit of a debate between game developers--Minecraft and Sims is an example of games using core mechanics like this, but these are extremely rare). There are probably some old games to look out for that might fit your criteria. "Super Metroid" for the Super Nintendo Entertainment System is pretty abstract, but the final moments of the game are fascinating to watch on how they tell the character's relationships with no use of words and all visual action. It might be hard to get since the game is so old, but maybe a youtube video might show the ending of that game (Don't rely on "Metroid: Other M" as that uses an entirely different method of delivering the story). Other examples related to the "Metroid" games would be "Metroid Fusion" for the GBA and "Metroid: Zero Mission," though the latter is less story-based when compared to the former.
Point and click adventure games are really worth looking into for this kind of class. They rely heavily on the narrative engine as a way of "rewarding" the player and come in a variety of ratings. The "Monkey Island" series are highly recommended here, along with "Grim Fandango" and "Day of the Tentacle."
RPGs are a little hard to recommend as their core mechanics does get in the way of the narrative engine, but JRPGs are a good spot to look for. "Chrono Trigger" is a great example. There are some "Western" JRPGs to consider as well, such as "Septerra Core" or "Anachronox." Those two should be easy to get off GoG.com right now and Teen-rated. Some RPGs are "story-driven" like BioWare games, but not every RPG. "Ultima 4" is free to download from GoG.com and is a fascinating game in exploring ethical consequences, but it has a steep learning curve and poor user-interface that the core mechanics might interfere with the story.
A lot of action games are probably best to look at in the current generation than older games, since most current games starting on the Playstation have developed the narrative engine along with the core mechanics. "Alundra" is an action/adventure game with a great narrative revolving around demons terrorizing and killing villagers through dreams, coming from the Playstation generation. Also action/adventure based would be the "Oddworld" games from the Playstation generation.
That is some games I can recall off the top of my head which might help with the class. Hope these help and good luck!
