I don't have a problem with linearity at all. If I want a really well done story, interesting characters, and good pacing then it's probably going to be in a linear game. I think you can maybe also make a tighter, more satisfying combat in a linear game. God of War III was a masterpiece, one of my favorite games ever, and it was extremely linear. On the other hand, I haven't really ever gotten too much satisfaction out of a very open, sandboxy game like Oblivion, although Mount and Blade looks pretty awesome.
I think there's room for both types of games. I think the modern trend is towards an obsession with choice and openness in games, but it can come at the price of story and characterization, and, in some cases, game play.
I suppose that some of my favorite games have been sort of a hybrid--games like Deus Ex and VTMB or other RPGs or RPGesque games where there's some choice but really wrapped up in a linear shell.
I also don't personally give a crap about replayability. I've almost never replayed any game. But I did just replay FF7, which is pretty linear but with lots of side quests and exploration. And I might replay God of War.
Of course, you also have turn based strategy games like the Civ series which are in a way some of the most non-linear games of all, and I do find those very satisfying.
On the topic of FF 13, since replaying FF7, I've realized that the (biggest) problem with it was not so much linearity per se but that 90 % of the game is combat, and the combat isn't very interesting at all. The new system did make it worse, but Final Fantasy combat in general isn't really that great IMHO, except maybe for boss fights. FF7 has some combat heavy stretches, but, unlike 13, it also has long sequences with no combat and exploration or mini games instead. If you're going to have mediocre combat, then you better have less of it and mix it up with more exploration, more NPCs, etc. FF7 would have sucked too if it was just 30 hours of fighting with some cut scenes thrown in.