While this suggestion can be added in 1.16.5, I was more imagining this getting added in a version of Minecraft that has the 1.18 caves. Those caves and the cave systems they make up are huge. They are fun to explore in vanilla, and I think it would be even cooler if I could stumble across a structure that I could obtain a Legendary Pokemon from, or if I could explore them for the purpose of finding one of those shrines. They don't have to be too common, but I should be able to find one by exploring one of the giant cave systems from 1.18.
As for the design of these structures, I thought the Regi and Treasure of Ruin structures would all be underground rooms, themed after the Pokemon obtained from them. If Diancie and Kyurem are given underground structures, I thought Diancie's would resemble the place with the Heart Diamond, while Kyurem's would be an icy cave. As for the generation of the structures, I thought they would generate around caves similar to dungeons. The Regi structures and the potential structures for Diancie and Kyurem may have parts of the wall missing like dungeons have, but the Treasure of Ruin structures would be intact as they are vaults.
I was thinking the shrines for the Regis would be more common than the shrines for the Treasures of Ruin, but a Treasure Map to a shrine for a Treasure of Ruin could be obtained from quests. I'm not sure how the Legendaries would be obtained, except that it would require finding the structures.