They don't *have* to be fun, but it helps if the developer is looking to garner an audience - ergo, to make a few bucks.
As games haven't quite hit the same stride as the film industry in terms of their overall production, I doubt we'll see something akin to, say, a Peter Greenaway flick anytime soon. A game version of "Prospero's Books" would attract the Lit Geek crowd, the Art Games crowd and a few critics with a propensity for this kind of stuff.
Would that project garner a huge following, though? Probably not.
Unless the team pulls a Dante's Inferno and somehow manages to take a riff on Shakespeare's works and turn it into some sort of weird shooter where Old Man Prospero has to heft a gun against Caliban or some shit, I don't see that happening.
There's just something about the medium's nature that turns the basic concept of fun into the glue that keeps some premises together, like Bulletstorm's. On the other hand, while Dear Esther is extremely daring and thought-provoking and while I consider it to be a novel experience; it's just not something I'll ache to go through two or three times in a row. This makes me question the validity of my paying ten bucks for something that's essentially over in one sitting.
On the other hand, Minecraft keeps on giving. I can keep rebuilding Shepards for the three Mass Effect games and experience things differently each time. Art games seem to be like books, in that while they might be memorable and deeply touching; they're designed to be linear because they're meant to provoke a very specific set of reactions.
In more traditional games, even the most linear of all setups can give me ample opportunities to be engaged differently, to approach things differently. Art games can be compared to novels, while actual games could be compared to Choose Your Own Adventure books.
So to me, fun is really a byproduct of choice. I can be engaged intellectually and emotionally by Dear Esther - but will I have fun? Probably not.