I like games where there's one main story arc, but a few different and (more or less) equally valid ways of getting through it. That way, if you only play the game once or twice, you still get to see all the important bits of it, but if you want you can go back and see what would happen if you turned left there instead of right, and stuff like that.
Personally, I think KQ6 has one of the best balances in linearity vs. er, open-endity. When you've played through it once, you've seen almost all the really important bits of the story... but then you can go back and there's a bunch of different things to try, all providing different nuances and such. It's more fun that way, IMHO.
And yes, obviously it's the illusion of freedom, rather than actual freedom. But that's what games are all about... illusion. I know that the creator's going to railroad me through their story... I'd just prefer they do me a favor and not make it obvious.

If a game is totally linear, I'll likely still enjoy it if it had a good story... but I'll also likely wonder why the creator just didn't write it as a book or movie instead. Much "easier" to tell a more effective story with those methods.
Although I will admit that I prefer a bit more linearity in adventures, and a bit more openness in RPGs.
Peace & Luv, Liz