"My problem with Zelda nowadays is that much of it is familiar territory. The dungeons are structured the same way (the weapon found in the dungeon will kill the boss, find it, kill boss, collect shiny thing) and then they have these ridiculous collection/trade quests outside of dungeons."
I only sorta found Twilight Princess stale because the overworld was so ridiculously similar to Ocarina of Time. It felt like I wasn't visiting new areas. That was Nintendo's choice though. They didn't HAVE to do that. I didn't have a problem with the concept of changing up the overworld in Wind Waker, just the execution. Legend of Zelda, Link's Awakening, A Link to the Past and Ocarina of Time all take place in Hyrule but the actually areas are quite different. Twilight Princess' familiarity is the exception and hopefully should remain as such.
I think if you took out the "go to dungeon, find item, kill boss" pattern it wouldn't quite feel so Zelda like. There's a barebones structure there that has to followed to some extent. The originality should come from the dungeon design itself and what the item involved actually does. And the "get shiny thing" again is just arbitrary. Nintendo doesn't have to reuse the flimsy "collect this many magic thingamajingies" plotline. They can think of a better reason to be in the dungeons.
I think Majora's Mask had the best way to avoid stagnation. There were only four "official" dungeons but so many of the sidequests had a dungeon like feel. They gave us something else to do besides the standard dungeons and that really made the game for me.