I think a good example of a procedural "adventure" game (by some definition), one where the procedural content promotes exploration, is Terraria. I think it handles many of the pain points that you outline quite effectively:
Procedural terrain may be straightforward, but procedural storytelling is not.
"Storytelling"? Terraria doesn't really do that. But it does have progression and de-facto quests (I'm not talking about fishing quests). It accomplishes this through a combination of factors.
Progression is not usually based on getting to a single, specific location. Terraria is a game about stuff, so progression is based on getting stuff: harvesting resources, opening chests, killing monsters for loot. Of course, resources, chests and monsters are all based on locations, but this is done in a very broad way. There are large biomes, and throughout these biomes, you'll find whatever resources are specific to them, randomly placed throughout.
There are elements of progression that are based on specific locations. But those are always generated in "specific" locations. Floating islands are always floating in the sky. The Dungeon is accessible from the surface on one side of the world, and the Jungle is on the other. Corruption/Crimson areas are many and it's pretty much impossible to miss them (unless the RNG was especially bad to you).
The least consistent place in Terraria that is important for progression is probably the Jungle Temple. And even that is not something you're likely to miss.
Procedural terrain provides scale without density.
That all depends on what you generate. Earlier versions of Terraria had problems with this. The underground areas could become very "samey".
Terraria, especially 1.2 and 1.3, solved this problem, making them incredibly dense with stuff. There's always something new to stumble across: ruined houses with chests, icy caverns, abandoned railroad tracks, underground lakes, underground desert, marble caverns, etc.
Density is created in Terraria through diversity. Instead of repeating the same content over and over, you repeat new contents. You have enough variations of content that the player doesn't get too bored.
What Terraria in particular does is that it builds the basic terrain of the world. Then the world engine goes in and randomly puts things in various places. A marble cavern here, a ruined house there, a shrine over there. The icy caverns go over there, a big desert sits here. The system is designed to be able to slot these features in anywhere in the world. That ensures that there is enough density of them that you won't get bored.
Now, the world engine isn't stupid. It biases certain features based on depth or distance from the center of the world (where you first spawn). But the main goal is to make sure that the game is filled with lots and lots of new stuff.
It may not make much sense why there's a ruined house perched above a lake of lava, but the player will appreciate that it's not just another cave.
However, diversity can only be achieved if the experience of play allows it. Terraria is an open-world game in which you can build lots of stuff. But it also has an action-oriented combat system that offers many dimensions of possible play. There are four "classes" (defined by what bonuses the armor you're currently wearing gives you): melee, ranged, magic, and summon. And within most of these classes, there is a large diversity of play options.
Ranged characters have a number of weapon types, but they also need to deal with the fact that they can't take a lot of hits, so they need mobility items. Melee characters need items that improve their ability to take hits. Magic characters need items that deal with mana regeneration. And so forth.
There are two important elements here: the diversity of play experience, and the lack of an enforced class system. The latter is really important, since it means that if you find a good melee weapon or a good ranged weapon, you can still use it even if you're not in ranged or melee armor. You may not be as effective as a dedicated build, but it's not useless to you. You can always try it out and see if you like it.
Plus, this means a "class" change is just an armor-switch away. If you get a good melee weapon, you can probably craft some melee armor and try out a melee build. If it doesn't work out, switch back to your ranger.
In this way, Terraria creates a game system where the diversity of exploration encourages a diversity of play, since there are a lot of options in the play experience. And vice-versa: diversity of play is what makes the diversity of exploration possible, since it allows the creation of a multitude of items.
The experience is not consistent.
This is where diversity and scale meet. Terraria achieves a surprising level of consistency in its overall play experience. While each individual world is different, the scale and scope of play means that you're unlikely to come up short on something important.
You're going to find enough Gold to make Gold Armor, if that's what you're interested in. You're going to find enough cobwebs to make spellcaster robes, if that's what you're interested in. Etc. All of the essential stuff is available in sufficient quantity. And thanks to the diversity of stuff, if you don't find one particular kind of thing, you probably ran across something similar to it.
Furthermore, there are a number of checkpoints you have to cross in order to move to another sequence of progressions. Surviving the Underworld is extremely difficult to do unless you have access to the Jungle/Dungeon/EoW/BoC-teir of equipment. You cannot shift your world to Hardmode unless you fight a boss in the Underworld. You cannot harvest Chlorophyte from the Jungle until you've killed all three of the Mechanical Bosses. And so forth.
Because of these checkpoints, you're encouraged to gather more resources until you can pass them. Which ensures that you have the chance to run across lots of various loot, thus ensuring a relatively consistent power level.
Now, that doesn't mean that inconsistency doesn't happen. Bad world creation can put you in a tight spot sometimes, or maybe you find yourself in a boring patch of world. But this is quite rare, thanks to Terraria's massive diversity.
The worst the world creator will do to you is feed you lots of the same resource.