To addendumize something I said earlier, yes, linear storytelling IS a design choice, but I don't think it's an appropriate one for a story driven game. Visual novels, while not having a lot of interactivity, focus the interactivity they do have onto the main focus area of the game -- the story. While they're also essentially linear, you still get to pick who dies, or what girl you end up with, or what information you get from where, or basically, how it ends.
The storyline is essentially linear and fully a product of the writers, but you have control over how it turns out/is presented to you.
And visual novels are an incredibly Japanese thing and not that much like western adventure games (which I need to talk about to). Which is why I think that it's more than a little odd that more JRPGs don't incorporate this kind of element.
I've recently been playing Planescape: Torment. While it IS non-linear in a gameplay sense, the main storyline is actually not that non-linear. However, you have different ways of approaching the various plot-points. If, for instance, a character, at one point, asks you to keep something they tell you secret, you can vow to do this and either honor or break this vow, or just lie about keeping the secret, or not promise anything at all, and this'll affect how the character, and the story, presents itself to you. Or at various points you have to pick between helping one faction or another.
Perhaps most interestingly is that a lot of sidequests and optional things can lead you into learning more about the nameless one's past. In this sense the player is involved in the story not because they have CONTROL over it but because they have to make an extra effort to learn some additional plot points -- and the gameplay reward for doing this is often more experience, too. A JRPG example of this would probably be CT's sidequests, as they were all VERY story relevant. Or maybe FFVII's think with Vincent's backstory.
Ultima 7, in a sense, is similar. Again, the storyline is fairly linear, but instead of entering a town/talking to an NPC and triggering a Plot Point into occurring, it's more about getting information and settings events in motion yourself. Ultima 7, despite not having a hugely non-linear/open-ended storyline, uses non-linear gameplay, world interaction, and NPC interaction to give the player a very active role in how its linear story progresses. I can't really think of any JRPG examples of this or uh really many non-Ultima examples of this.
Ultimately, I think the goal should be to involve the player in the storyline as much as possible, if that's your goal. I tend to think that ultra-linear storylines, much like featureless worldmaps and random battles, are kind of an unnecessary throwback to the days when it was hard to do the alternative well.
Comments on Gameplay:
One of, or perhaps in a JRPG context the GREATEST, asset of non-linear gameplay is that it overcomes the problem in grinding. I've mentioned this elsewhere, but in Dragon Quest 4, I happened upon a storyline boss that I HAD to beat to progress, but was a bit under-equipped and under-leveled for. Being in chapter 5 and having the boat, the game was fairly non-linear, so instead of doing the boring thing and grinding, I went off, explored, and found some hidden items.
Non-linearity isn't just being able to do dungeons whenever you want, although I am fond of that style (and if you need a more controlled way of doing things, just... occasionally have moments where the player can do three or four dungeons in whatever order they want.) It's also in things like character advancement, like, not having a linear spell progression but rather being allowed to allocate skill points as you see fit, or being able to class change, or being able to convince demons to work with you instead of getting new party members via plot points.
Also, weapon advancement is still a very linear thing in almost every JRPG and it kind of bugs me. I'm tired of the "get to new town, replace everyone's weapon" setup.
I also don't believe on placing artificial restrictions on player movement, especially in regards to backtracking. If you want to block them from going forward, fine, but never shut them in an area if at all possible. (I also believe that giving the player new abilities to get past an obstacle -- like a boat in a dragon quest game, or a tool in Zelda -- are better than having plot points remove obstacles. Again, player involvement. Although this is still essentially linear design. Hm.)
I think the other huge merit of non-linear gameplay is exploration. Let the player go off the path and look for treasure. Let them experiment with other skills and spells. Let them find secrets and hidden things. This is what I thought was so cool about DQVIII. Sure, very linear game, but between towns, out in the field, you could look around as much as you want and find all KINDS of things.
I'm also not a fan of TOTALLY non-linear gameplay, like in Daggerfall. It's so wide-open that it tends to lack any sort of clear human touch.
Comments on Adventure Games:
The lack of openness in solving puzzles in adventure games is why I don't really like them anymore. Most point and click adventures, especially, have really limited puzzle solutions. Even a lot of text-adventures have limited solutions. This is why I didn't like the Longest Journey though. Story-driven, but no real control/involvement from the player perspective in the story from what I recall, and the ppuzzles all were single-solution things and the solutions weren't even that sane.
Part of the problem is that you have to consider the personality of the player character. They might now do something that the player would, or would do something that the player wouldn't.
One of the better examples of having multiple solutions I've seen is the old BBC-A sidescroller/metroidvania, Exile. In Exile there's this underlying physics engine behind everything so you're pretty much free to use EMERGENT GAMEPLAY elements and physics to do whatever the hell you can think of doing.
Also, despite not having multiple solutions so much, I like the puzzle design in the Myst games because they generally present you with machines that you have to learn how to use, either by fiddling with them and observing, or finding an explanation somewhere. Again, I think this involves the player more with solving them -- and involvement is the key goal -- because it's not just a matter of finding Key Item X and using it on Key Item Y, but rather a much more interactive process. Aaaand Myst games tend to do a good job of reacting to what the player does. Most notably Riven and it's several million bad endings that happen if you do something really stupid.
The last FF-game fight that made me think (besides optional bosses) was one of the seymour encounters in FFX where you have to zombify your party. Otherwise it was kind of simplistic overall..
FFX tended to have a lot more puzzle bosses, and I found them harder than I probably should've because I was approaching them from the normal FF mindset -- buffing is uselss, strategy is useless, etc. So I don't know if FFX is really more strategy driven, with the puzzle bosses, but it is a rather more involving.