The game design it self became infuriating. The exploration was mediocre at best. It always pointed you in just one direction,with such little freedom. Even in dungeons there was only one path it became very boring with little replay value.
I've thought about this a lot and actually the most nonlinear component of Skyward Sword seems to be the dungeons at least from my perspective. The overworld is really linear the first time you go through areas, and then they let you move around to collect things (kikwis, key pieces, and generators). So they don't let you explore the first time you see things, but then give you some freedom once you've seen everything. Even the some of the sidequests unlock sequentially. The dungeons actually range from extremely linear to fairly nonlinear which is surprising considering how the rest of the game was designed.
Lanayru Mining Facility, Ancient Cistern and Fire Sanctuary are all very linear- you can't really do much different in terms of the required content from playthrough to playthrough. However the rest of the dungeons offer at least a little freedom. When you go into the first water room of Skyview you can choose to tackle the left or right room first. In the Earth Temple, unlike the other dungeons in the game, the dungeon map isn't directly in your path to the end of the dungeon. You can get it whenever or skip the room it's in entirely. The Sandship gives you two objectives in the generators, and there are a variety of different orders in which you can tackle them. Also you can skip the map easily, and it saves a lot of time to do so. I spent a lot of time analyzing the dungeon, and my third playthrough was very different from my first thanks to the freedom offered in the dungeon. Sky Keep is just really nonlinear and it's easy to see that. These dungeons aren't incredibly nonlinear like Skull Woods in A Link to the Past or other dungeons from that game, but they seemed less linear overall than dungeons in Wind Waker and Twilight Princess at least and maybe Majora's Mask as well. Just my opinion though.
Overall dungeon linearity is getting pretty obvious though in the console games. If my memory serves me right there is literally one dungeon (Hyrule Castle in Twilight Princess) post-Ocarina of Time in which you can even carry more than one key at a time. The only other exception is that Majora's Mask lets you replay dungeons with keys reset so the dungeons become more nonlinear with items you didn't have the first time around (best example: play Snowhead with the hookshot and look for torches on ledges to hookshot).