Author hasn't listed Noita which is a recent game. Levels are fully destructible and procedurally generated. Every play through feels different mostly because you discover some item you never had before. Pixel Dungeon is an Open Source roguelike dungeon crawler with procedurally generated maps. It also has high replay value because every play through feels different.
(mild spoilers)
Once you figure out that the world is actually much bigger than the normal levels you go through the game also has a big exploration element: you not only need to find spells to defeat enemies, but also to traverse the terrain and access secrets. There are cryptic messages hidden in places behind terrain, hidden combinations of liquids that have powerfull effects, secret artifacts that have to be interacted with in a certain way.
Nowadays if you see someone playing this game online you'll see them do all these things, know where to go and what to do. But when the game just came out almost none of this was known; people had to figure things out on their own and worked together in the Noita lore discord. I really liked being a part of it.