There are different ways of structuring a story, which I applied to structuring a game hypothetically.
Straight-up linear means there's only the line that you can take to your objective. Those are your modern shooter campaigns, a lot of other games like that. Goes without question that these games are linear. Roguelikes aren't even this linear, generally.
There's a network structure, where there are a lot of "rooms" linked together, and your objective or objectives are somewhere within it. You can freely move between rooms, but in the end, all it does is let you choose your path to a goal. This, to me, is the most nonlinear structure, and it's the kind of thing that I'd say Valley 2 or Elder Scrolls are closer to, in terms of how the world works. In Valley 2, you have that objective, but a large network that is the game world to navigate in order to determine how best to reach your goal. Pretty nonlinear, in that respect. In Elder Scrolls, I'd say it's more the world that's a network. From what I recall, the storyline itself is just a linear chain of missions. That's kind of why I dismissed open world games. The story and goal itself may actually end up being just a linear series of missions, with a whole load of side missions that you can do that don't really have an impact on the story at all.
There's also a foldback structure, where you can take any branch or route, but the story or levels always fold back to the same conclusion at fixed points. Thus, in the end, you're still going towards the one thing point and never stopping. This is what Mass Effect does. In the first two games, it all comes down to what you put in, what endings are available to you, so it folds back into multiple points. In mass effect 3, it folds back into one point, which splits into 3 endings.
Then, I remember something of a web, that ever-expands and branches outward forever. But, putting a goal in a mess like that means that there are only a few routes you can possibly take to it. That structure only really lends itself well to multiple-ending kinds of games. I'm pretty sure Shadow the Hedgehog is a good example of this. Every level has multiple ways to finish, and each one leads to another unique plot point, which comes down to hundreds of (extremely similar) endings.
What I was mostly getting at is, in terms of actually setting a goal, the way that you take to reach that goal will end up being more or less a straight line path, except for the very unique case I guess of Valley 1/2 and AI War. However, those games seem to have little storyline structure. You couldn't really work in a lot of dialog or cutscenes or story because of how uniquely the game can be played from person to person. Even Valley 2, as I understand it, has several foldback points that end up working out about the same way, no matter how you actually end up playing (unless you outright failed). You always have to level up your spells. You always need to get the movement upgrades. You always need to destroy the crystal and kill Demonaica (presumably). In the case of AI War, it's mostly a case of "Blow up these two buildings however you want I guess". It's very compelling, sure, but that's what it comes down to unless you go Fallen Spire, which is story-driven and structured and gives you one goal after another.
I've given it more thought last night and today, and I think what I really mean is, the more of a goal you have, the less freedom the game can offer you. If you've got a structured story to tell, you're always going to just be going down to the next level until you win. In the case of roguelikes, there's some reason that you're in the dungeon, and generally it's because something is entrenched at the deepest level. There aren't many ways to really make that nonlinear. You're always going to finish one level after another, with some slight branching and then a foldback into the stairs down to the next level. The way I figured you'd be able to make it work in a nonlinear fashion is if there are a limitless amount of dungeons and quests to hop between. You decide, "Okay, the Dredmor Dungeons are boring, I think I'll head to the Ice Caverns of Mim to recover the legendary Sword of the Familiar." Thus, you have a lot of tangible goals and you can switch between them at any time.
But then, suddenly, gameplay balance is a very real issue.
...If you stuck with this post all that time and understood it, thank you so much for that. This post is so terribly organized, because you made me really have to think and reconsider and analyze to write it.
