1. The feeling that you're playing your own game. If you thoroughly shuffle a deck of 52 playing cards, chances are overwhelming that that particular arrangement of cards has never existed before. I like the same feeling in a CRPG: that the game I'm playing has never been played by another player. No other player has ever exited the Oblivion dungeon, headed back to the prison to try to turn himself in and, finding no recourse to do that, punched the guard on duty so he could be arrested and finish serving his sentence. But I did, last time I played.
2. Honest-to-God role playing. Why did I do that sequence last time I played Oblivion? I decided my character was going to be an ex-guard himself, committed to the principles of law and order, who had made a bad decision and was suffering horrible guilt for it. In that game, you can invent such complex characters and role-play them accordingly. In Baldur's Gate you can (at least for a time) decide you always hated Gorion and head off in a random direction looking for gold. Or you can develop a pathological hatred for bandits and spend hours patrolling the Sword Coast collecting their scalps. Ultimately you have to capitulate to the main quest if you want to "win," but non-linearity allows you to do it the way you want to do it.
3. Backtracking. Ever visit your old High School and walk its corridors, using the experience to gauge how much you've changed since then? You get some of the same feeling wandering the streets of New Sorpigal (in Might & Magic VI) after clearing out a map full of dragons. Remember how the goblins in Goblinwatch gave you such trouble when you were level 1? Well, they've re-spawned since then. I love taking my level 30 characters into some dungeon on the first map and committing nonstop slaughter of my erstwhile archnemeses.
4. The joy of exploration. Most nonlinear games--though not all--seed their expansive gameworlds with interesting things to find and do, including plenty of side quests. Baldur's Gate has a village of Xvarts for no other reason except that you stumble upon them and have to decide whether to slaughter them or flee. In another map, you're wandering along through the forest and see a statue of a fighter in the middle of nowhere. Just as you realize "hey, that's not a statute!" here comes a basilisk. That's CRPG gold.
5. Replayability. This reason builds on the other four, but it's still worth mentioning. There would be no reason to replay The Bard's Tale unless enough time had passed that you simply forgot it. By allowing you freedom of movement, however, and the attendant role-playing and exploration that come with it, you could replay some games dozens of times and create new experiences each time. The funny thing is, I sometimes don't capitalize on this advantage: I often struggle to keep myself from playing a game the same way I've already played it.