Is that perception really the truth though? Isn't it more likely that you condoned flaws of the formula because there were so many Zelda nods present that the legacy made the formulaic games better than they really were?

Well, this should be further examined. A Link to the Past doesn't follow a formula of "find item in dungeon, use item to solve puzzles in dungeon and to defeat the boss." It can be somewhat like that at times, but it's nowhere near consistent enough to qualify as a formula.

The aforementioned formula first appeared in Link's Awakening which I think of as a method to make a more linear game more interesting and because the enemy count had to be reduced due to Game Boy hardware (processing power and screen size/resolution). Similarly, this formula was used again in Ocarina of Time, only with more puzzles to accomodate for the difficulties in creating 3D games. Combat wasn't going to feel as good as in 2D, but puzzles weren't as hard to implement in 3D. The early limitations of 3D either vanished or were eventually solved, but Zelda continued the formula regardless.

My point is that this formula is and never was an essential part of Zelda. It was a solution to actual problems that existed at some point in time, but it took a life on its own when it wasn't needed anymore. You could say that Zelda was handcuffed for a long time and then Breath of the Wild got rid of the shackles.

I think in order to retain the open world freedom and non-linearity of BotW, dungeons would have to be closer in style to Hyrule Castle than Vah Naboris, for example. I think themed dungeons and dungeons that grant powerful, potentially game-breaking items are out. Instead they'd have to be ruins or castles or catacombs with tough enemies and lots of treasure and maybe weapons/shields/bows to collect. 

In short, you wouldn't have [insert themed temple] where Link gets [insert artifact that beats dungeon boss]. You'd have a lot of optional monster-infested dungeons with rewards in the form of rare weaponry and valuables.

I don't think Aonuma had much say in this. Breath of the Wild is similar to Twilight Princess in that Zelda was adjusted to the market's wishes instead of Aonuma's (who would have continued with the art style of The Wind Waker). When Nintendo's financials are below an acceptable level, the business suits call the shots instead of giving the developers freedom. Shigeru Miyamoto didn't get removed from the hardware design by accident either.