Linearity isn't a problem. Railroading is. Most people seem to use the terms as the same thing nowadays, which is wrong.
The difference is that linearity has to do with the story. GTA is as linear as it gets. It is however not railroading the player, that much (except when you're on missions). As another example is Spellforce. It's supposed to be a rpg/rts, which should involve choices. The only choices you usually have is what units to build, because there is, in the whole game, always ONE way to go. You can't go around the enemy and attack them in back, you can't attack someone else. There is always one way, and one way only to your goal. That is railroading.
And there are non-linear games as well, and some games that fall a bit in between. Fatal hearts is a great example of a non-linear game, especially since that game is all about the story. You can't escape the story at all, everything about the game is that story, and still, it's not linear. Sure, you do many of the same things on a second playthrough, but in some cases your choices really matter. You can choose which side to join, for one thing, and it's done in a very discrete way, on your first playthrough you wouldn't be able to tell that you could, you'd think that there only was one possible way.
Neverwinter nights also has a good example. It's awfully linear. It has one alternative about how things can go. It doesn't railroad you into this however, but lets you choose how you go about it, very freely. A lot of things depend on your choices as well, you don't have to kill everyone.
I've never had a real problem with linear games, as long as they're good, I don't care. But railroading games however are really bad. If there is always only one way to go, always only one solution to every puzzle, and you're punished by trying anything else, then it's a bad game, unless it has an amazing story and gameplay.