Zelda has a strange history from a certain POV.
Ocarina of Time is seen by many, many people as epitome of the core Zelda formula and design concepts. But compared to non-3D Zelda games it has a lot of problems and limitations: such as its terrible and almost non-existent overworld, to slow and awkward forced sequences gating access to the next dungeon. But the novelty of it being 3D really burned itself into popular consciousness.
After Ocarina, there was never a 3D Zelda game it seems everyone was really happy with.
Majora's Mask: too mechanically strange and thematically weird for many.
WInd Waker: "Celda", sailing mechanics, padding, bad endgame, few dungeons, incredibly easy.
Twilight Princess: Dull brown art direction, by-the-numbers, feels too long, interrupting wolf sequences
Skyward Sword: motion controls, repetitive boss sequences and once again a bad "overworld", lots of dungeons but few unique areas.
Essentially, after Ocarina of Time and before BotW there wasn't a 3D Zelda that the audience seemed generally happy with. Every game was criticized for being pretty flawed and frustrating.
Only the 2D games seemed to retain high approval through all this - except for the two touch-screen games for the DS, due to their highly experimental mechanics. And how different The Adventure of Link is (but it has a strong fanbase). Compared 3D Zelda, it's nearly universal love for:
The Legend of Zelda
A Link to the Past
Link's Awakening
Oracle of Ages
Oracle of Seasons
The Minish Cap
A Link Between Worlds
Personally, I think what the general audience was unhappy with and perhaps blaming on "stale feeling" was the 3D games missing a key element from the 2D side: a robust overworld and feeling of exploration. Even Twilight Princess didn't do a great job of this - Nintendo seemed afraid of a 3D overworld with too much combat or time spent outside of dungeons.
There's some irony here, in that the number 1 complaint about Breath of the Wild is its lack of traditional Zelda dungeons. On the other hand, BotW seems to have massively served a longstanding desire for a 3D Zelda game with a proper overworld and tons of self-directed exploration. I wonder if the enthusiasm for this aspect of BotW has reframed the conversation towards "Zelda players wanting something radically different", when it's really "Players bored and frustrated with 3D Zelda never translating a core element of 2D Zelda."