I'd posit that the existence or absence of win conditions or failure conditions can't determine whether something is a game. Tetris lacks a win condition, along with numerous early arcade games. MMOs almost universally lack failure conditions - that is, it is generally impossible to lose at an MMO. You can "die" but it generally only temporarily inconveniences you.
IMHO a game is anything interactive that you play for entertainment. Movies? Not interactive. Books on tape? Not interactive. Choose your own adventure books? A game in book form. Visual novels? A game in book form computerized with visuals, right? So this definition would probably be more broad than the ones that were proposed earlier in the thread.
This is a thing from the 80s, which definitely was a game in book form (It had stats, equipment, even a spellbook you were encouraged to try to memorize pre-adventure and then never look at again because you couldn't bring it with you on your adventure):
http://en.wikipedia.org/wiki/Sorcery!
On the subject of sandbox games vs linear games:
A funhouse is a linear sequence of scares. "Take it or leave it" is the only choice given. Makes you think about free will. Had our choices been made for us because of who we are?
I feel like sandbox games tend to lack strong stories, requiring you to make one yourself, and while that can be fun, you can run out of motivation to keep playing (and skinner boxes really don't do it for me).
I like games with good strong stories, especially when they let you make choices in the course of them, shaping the events as they proceed. If they're overly linear, where you've got no choice, it's less great, but if the story is amazing then I won't mind.
Some games seem to put no effort into the writing or quest design, ending up with a terrible story and quests (most of which seem to be generic fetch/deliver/kill quests that send you across the map), apparently in the hopes that it'll be overlooked because they've got sandboxiness and moddability (SKYRIM SKYRIM SKYRIM).
Edit: Damn, I was trying to
avoid making a long post.