Both can be executed well, both executed poorly. With western RPGs I usually prefer nonlinear gameplay because it really puts the character and story in your hands. Mass Effect had a great nonlinear gameplay system. You can do the first two-thirds of the game in any manner or order you see fit. Once you trigger the climax, the gameplay becomes pretty linear, but necessary to resolve the plot. And the climax is pretty clearly marked, so you should be able to finish any open assignments or just explore until your heart's content before you beat the main storyline. Mass Effect also managed to keep the sense of urgency about the main quest, even while you were off completing side assignments. This is something other nonlinear games forget sometimes. Like Oblivion. In the opening act, the emperor is murdered and you're charged with finding his heir. But if you choose to go off and rule the fighter's guild, no one really seems to care about an empire in chaos. Some people mention the emperor's death, but that's it. You only get a sense of story and urgency after you advance far enough down the main quest line. But why would you want to? After the emperor's warning, no one seems to care what you do.
A good nonlinear game still remembers the main quest is most important, and usually threatening the safety of the world/empire/galaxy/whatever. While you can complete other missions and tasks as you see fit, they should somewhat tie into the main crisis. They should at least help immerse you in the surrounding worlds. When a game does that, like Mass Effect, the result is something I find preferable to a linear story. But when a game fails, like Oblivion, I would rather play a better-paced linear game. Good pacing can exist in an open world, you just need to work at it.