I have some serious issues with
Milen's viewpoint - at least the long list of his percieved "failings" of a linear, story driven game. I will concede that some story-based games are overarchingly
linear, some not offering any
plot branches at all. And yes, the player's freedom has to be limited. This is simply a fact that has to be accepted to make this kind of game practical.
However, I would argue that even a game suffering all of these characteristics, you can still derive hours of enjoyable gameplay (and even replayability if the writing is good, and if there's enough optional stuff to discover). In the service of entertainment, some distance from reality must be maintained : we don't go to the cinema to see Batman stay home for the night watching TV.
Regarding the role of randomness in these games : the thinking behind this is that the game's story has to be modelled after a linear form of media, to retain a sense of progression. This can limit the player's freedom. There are a number of solutions to this. Elite drops plot entirely and is still awesomely playable. Final Fantasy on the other hand crams random encounters down your throat by way of compensation (and yes, this soon becomes tiresome).
I would disagree that there has been a net shift toward "booklike" games. Racing games, Fighting games, FPS's, RTS's, and goofy stuff like Chu Chu Rocket and the rhythm action genre are all purely "gamelike". The only solution to the percieved "softness" of current story driven games would be to never allow reloading after death (a la roguelikes and Championship Manager, and the first version of AvP), which I would welcome, but most casual gamers would hate. The reload problem, as it is known, is the largest single obstacle remaining in today's polygon-saturated gaming world.
A classic game, for me, is one that manages to successfully combine both booklike and gamelike parts, or pulls off one of the two so well that you don't notice the lack of the other.