Well going back even further in the days of the Spectrum, C64 and Amiga the games, for me, had to have a good story. Some were very basic like Treasure Island Dizzy (getting shipwrecked and trapped on a Treasure Island and having to escape) to Dungeon Master where they wrote 30 pages in the manual about what happened and then continued this theme into Chaos Strikes Back.
Nowadays and I class Half Life amongst them - it's a very basic storyline. Aliens invade you are the only person who can stop them, yadda yadda. It's nothing inspiring there. Galdregons Domain, BAT, Hunter, Monkey Island, Captive, Supremacy, The Last Ninja, Infiltrator, Legend of Valour, Spellbound, Bloodwych, Robin of the Wood, etc. all had very good stories and had some very nice instruction books. They made you think that when you were playing the game you were making a difference and affecting something rather than just being along for the ride.
M.