The use of story and what is or is not a game, has been debated on various forums on the Internet. In order to address this debate, I figured I would look at what I see as a spectrum of play and forms of entertainment. 

I see the spectrum going as follows (open-endedness vs narrative driven or structureness):
1. Toys and simulators (vehicle and world simulators). These are things you play with with no point in mind. You have a degree of control over them, and make them do what you want. These aren't too frequent in videogames although something like Noby Noby Boy would likely fit here. If a game comes with a development language also, to create content in a very open way, it could be considered part of this also, like something like Kodu. I would put Sony Home here (excluding the in world games), as is Second Life. Will Wright specializes in these with his Sim series. On the other side of this would be a program like Microsoft's Flight Simulator.

2. 4X and strategic world simulations (and god games): These games are like Civilization (4x: Explore, expand, exploit, exterminate), or a business simulation like Railroad Tycoon. In these, a player controls a world, like in the Sim series, but use strategic to achieve goals set by the game.

3. Sports and boardgames. These are competitive ventures, where the object is to use the play area to defeat an opponent. The approach is fairly wide open, but the goals are set. Not as open as sandbox games, but still more open than other formats of play. Chess would fit here, as would RTS (and turn-based RPGs), or sports games, or games like Settlers of Catan. Fighting games definitely belong here to, as do driving games, and also multiplayer FPS. The focus here is player vs player, and players can continue to evolve new strategies.

4. Sandbox games. These are open play areas, aka a sandbox, but will have puzzles or other challenges in them. Sandbox can fit Grand Theft Auto or Crackdown or inFamous. The former ends up likely having more story put on top, while the later gravitates towards the toys/puzzle category. Western RPGs can fit here also, depending on the open-endedness (and how dynamic the world is). I would say LittleBigPlanet may fit here actually, or anything with a level editor for it. World of Warcraft likely fits here also, or other online RPGs with a world that dynamically changes. In short, the game world is open, and there are structured missions in them, including free roaming openness. 

5. Puzzles/classic arcade games. These are like toys, but are goal driven, in that you need to get the toy to a certain state. Tetris can be seen as fitting into this. Classic arcade games like Asteroids and Space Invaders would fit into this here also, as do games on the puzzle side like Tetris or Bejeweled. Rather than solve problems, you continue to play at them. These games lack the open-world structure to them seen in sandbox games.

6. JRPGs and single-player part of FPS titles. These are fairly linear in nature, but some can be less linear for players on a whole, and can involve some alternate paths.

7. Post-arcade console action-adventure games, with endings and levels. Sonic, Mario, Zelda, and others that we know, fit here. The games have endings, and don't go on indefinitely. This is the classic videogame as we know it.

8. Adventure games and interactive fiction. These are very strict in how they are laid out and linear in nature. Text adventures fit into this, as does a game like Myst, and the graphic adventures of Lucas Arts. And on the more strict end, a game like Heavy Rain would fit into this also. For individuals heavily gravitating toward story and character, this is a place they would consider this the best form of play. I would also count Uncharted in here also (single player).