Ernest Adams has written a fantastic article for http://www.next-gen.biz about the "50 Greatest Game Design Innovations". There is tons of good content here to get you thinking, mull over, and argue about. Take a look at it here: http://www.next-gen.biz/index.php?option=com_content&task=view&id=7769&Itemid=2
Here are some of my comments about the entries:
Ernest says that the "first known us is unknown" and one of the comments tries to cite "Metal Gear in 1987", but most students of game design and classic games would have to throe-up "Castele Wofenstein" by MUSE, released in 1980. One of the best strategies in that game was donning a Nazi uniform and sneaking by the guards.
9. Dialogue Tree
I'd have to say that the dialogue tree in Ultima IV was one of the first uses of great dialogue system.
12. Multiple Skill Levels
Early Atari coin-ops allowed the arcade operator to set the difficulty level of the game, mostly to make more money. The Atari 2600 launched with the "Difficulty A-B" switch that allowed players to alter the difficluty of games based o ntheir skill level. The first use that I can recall was in the 1978 version of Breakout for the 2600. the difficulty switch changedthe size of the paddle.
17. Interactive Drama
All roads to and from this lead to Chris Crawford.
23. Gestural interfaces.
I would think the Power Glove would fit this category
31. Procedural landscape generation.
"7 Cities Of Gold" indeed. One of the lost classics of the 8-bit era.