I notice a lot of you say the stories get "better" as the games progress.
Red and Blue. You battle team rocket. Cool. There's a Charizard and Blastoise on the cover.
Then come the games based on the legendaries. There's Ho-oh, Lugia, then we've got Kyogre and friends, the Giratina trio, and there's the Kyreum krew. Maybe the story being based on the legendaries is ruining the "go wherever you want". In no way were Zapdos, Moltres, and Articuno in any way relevant to the storyline. You could catch or faint them, no problem. Everything seemed to be like that in Kanto. I quite liked it, actually. In Johto, there was enough end-game content that made me think "fine, okay" (they probably should do that more to help with the linearity, FR/LG's Sevii islands helped a lot).
I don't think my problem is the linearity, the problem with me is the "Legend-based" storyline. It's tiring, and not getting Mewtwo till afterwards with a few notes in the Pokemon mansion made it more mysterious and you had something to look forward to in the end. What's the point if you beat the gyms, the enemy, and caught the best Pokemon you could before the game ended?
I'll use FR/LG as an example again, since they did such good work. You had to get an in-game thingy (the Ruby and Sapphire) before you could even trade with R/S/E. That was cool. And you could catch Mewtwo, breed Pokemon, and flush out the last of TR. It was all Johto Pokemon, with Johto music. If at the end of B/W, you were shipped to some islands playing music from R/S/E with about 40 Hoenn Pokemon to capture, I'd be happy. But I felt as if end game was an afterthought for the 5th gen in general (and for HG/SS, but that's a different topic). Ruby and Sapphire's endgame content was nonexistent, (and that stupid battle frontier was stupid, though finding the other 2 Legendaries in Emerald was fun--or would be, if I weren't afraid of losing all my Pokemon in my Nuzlocke).
I believe the end game content is just as important as linearity, and with linear end game (minor, like being able to go to all seven islands but not needing to be on all of them in a certain order), the game just lasts. I can't play R/S/E over and over again. I can play Sinnoh a fair amount of times without being bored, and the sequels to B/W were boring, even though things were changed up (you should have been able to go whichever way you wanted in the first place). I don't think I need to mention because of the pre and end game linearity, I was able to find a diverse team of Pokemon to battle the league in whatever order I wanted to. (Besides the 3 legendary birds and Charizard, there are (for a flying type necessity of mine) Pigeot, Fearow, Farfetch'd, Dodrio, and you can get them all once you get through Rock Tunnel). I could get whatever flying type I wanted early enough in the game to maul Erika.