This way, you’re still free to discover any shrines at any point, but if you choose to follow the plot points of a main quest narrative, a select few of those shrines transform into traditional dungeons (perhaps even novel items in each).
The combination of multiple shrines with similar themes into bigger, dungeon-esque shrines like "Trial of Power" or "Blue Flame" is very appealing. But I don't think that they should be formatted as shrines; if they were to be found naturally in the world, it would make these quests mean more.
However, I've never liked the argument that BotW doesn't have "classic" dungeons. While they don't "feel" like classic dungeons because they take place in the overworld, the amount of scripted Shrine Quest content more than makes up for the lack of traditional opening puzzles - mini boss - item - ending puzzles - final boss design. Thyphlo Ruins, the Lost Woods quests, the three labyrinths, the Forgotten Temple, the Hebra and Gerudo Great Skeleton, Eventide Island, Mount Taran, Kass's riddles. All that content combined adds up to the dungeon content of other games, at least as combat is concerned. And, because of the physics system, every combat encounter can also act as a puzzle.
But if you want specific puzzle content, there is a tremendous amount found in the shrines. They get a bad wrap generally because most are so short, but adding them all together results in the puzzle dungeon content of other games.
I also don't think the Divine Beasts get enough credit. Yes, they have some easy puzzles, but the last time Zelda had hard dungeon puzzles was Oracle of Ages so I don't really mind. And the freeform nature and complete control of the moving pieces is a completely new and fascinating take on Zelda dungeons, while still having a somewhat natural progression throughout. The only difference is that the "item" (Champion ability) is gotten at the end of the dungeon rather than in the middle.
The real issue with BotW dungeon content is that the copy and paste nature and short-form experience of the Divine Beasts, the Shrines, and the Shrine Quests don't allow the content to
feel like a Zelda dungeon. This is why the randomization of plot-based dungeon-shrines wouldn't be that effective: you still wouldn't be solving the issue of these challenges not feeling like dungeons. I think that, instead of the ability to get to all shrines, you get rid of the concept of a blessing shrine and just add more challenges to the natural landscape. Because you'd end up with the same result: specific shrines designed for the completion of a specific challenge, plot-based or otherwise.
But the integration of challenges into the fabric of the world, like the Yiga Clan Hideout, would make these dungeons have that appealing Zelda-dungeon game feel. That's what I would prefer: plot-point-based challenges that are not capped by "dungeon shrines" or, in a worse case, "blessing shrines." This would make these experiences more meaningful and more in line with both Zelda philosophy and Breath of the Wild philosophy.