What goes into an RPG dungeon?
Rooms that are arranged in a way that makes sense. A bunch of little backstory elements strewn around for flavor, like a dead adventurer with a diary on him. Encounters in these rooms that are interesting and challenging, rather than the same copypasta over and over. Creative use of traps and secrets that can be detected by paying attention to the environment. Maybe even a bunch of puzzles. Unique items to find after defeating the boss, with cool effects that change your approach to combat when you use them.
Every single thing in that list can be done procedurally, nothing preventing it.
Even puzzles. Though they shouldn't. Fuck artificial puzzles (like plates, levers, word guessing, etc.) in RPGs.
What goes into an FPS map?
Complex 3D architecture that looks cool and allows for a lot of vertical movement. Placement of weapon pickups, health, ammo. Placement of enemies to create challenging combat encounters. Placement of traps and secrets, remember how many fucking secrets there were in games like Quake and Unreal?
Again, all of this can be done procedurally. Secrets, especially. Secrets in these games are usually the results of "hey, there's some unused space", "hey, there's a nice possible shortcut here", "hey, this place lacks something special", etc. All of which can be logically detected.
The problem does lie in the complexity of the architecture, though. A level from a game like Duke Nukem 3D or Blood procedurally generated? Sure. A game like Dishonored? No, would take too long. Though even that would disappear if CPUs become much more powerful.
What I could imagine in the more complex case would be a procedurally generated level for something like Dishonored, but it's more simple and the level designer can flesh it out - to save production time. Might be an interesting experiment to combine both.
What goes into a quest?
A) An open approach with multiple solutions and multiple endings, ideally. Choice and consequence. B) The option to play through as a diplomat, a thief, or a fighter. C) Interesting characters that give you some non-generic task to do. D) Factions that change their opinion on you based on how you act during the quest. E) A unique, worthwhile reward that doesn't just seem generic but is actually connected to the quest you just did.
Everything in this can again be done procedurally.
A) and B) are more the result of core gameplay systems, though. Imagine a quest in which you have to enter a house and get item X. A procedurally generated, realistic house would be naturally compatible with multiple approaches if NPCs can simply be talked to, sneaked around, pickpocketed, killed, bribed, etc. Multiple endings can also be part of a procedurally created quest, absolutely nothing preventing it. This isn't usually done, because even "hand-crafted" quests do not usually feature multiple endings at all.
C) is probably the biggest problem here, which ties into procedural stories being hard to pull off. However, hand-crafted characters (or character-arcs?), procedurally placed in the world would not be a problem.
D) is not a problem, as opinion in the end is almost never more than a score that gets higher or lower depending on how you act. And how you act can be logically checked based on what you do and who you do it with.
E) I really don't see how this would even be a problem in procedural generation.
Those are all things you need an actively thinking human mind for. A designer who knows his shit, who knows what he wants to do with his dungeon/quest/FPS map and knows how to achieve it. Not just a random combination of several elements, but a purposeful design where every element is at the exact place it needs to be. Not strewn about randomly, but with purpose. And that's what procedural generation can't do. It can't make up a big plan for something and then deliver that with purpose behind every element. An algorithm is not going to think, "I will now work on an ancient abandoned temple constructed by an antediluvian race, where a demon-worshipping cult is trying to resurrect evil antediluvian gods using the rituals they found inscribed in the walls of that temple, and as you explore the place you will first encounter cultists, and the deeper you go the more ancient demons and fish-monsters you will encounter, until finally meeting the high priest surrounded by an army of summoned Lovecraftian horrors; throughout the dungeon you will find little tidbits of information in wall inscriptions, old clay tablets, and murals that give you hints as to why the antediluvian civilization collapsed; in some rooms in the dungeon you will find appropriate special encounters like a young noblewoman from a nearby city being chained to an altar as human sacrifice, and you can free her, or a room where initiate cultists are studying the language of the ancients".
Completely wrong.
A sufficiently complex algorithm could do exactly that and "think" exactly like that.
No, that's what a human designer who knows what kind of dungeon he wants to make would think. An algorithm would just combine random elements that it's been told will fit together, but it won't do so with any kind of purpose - it will only do so because it's been told "Lovecraftian fish monsters fit well together with Atlantean wall textures".
Oh, ye of little faith.
Your problem, as usual with this thematic that you do not fully grasp, is that you think algorithms are necessarily only producing something based off a very simple ruleset and cannot be purpose-driven.
Which is simply not true. Imagine procedural generation not as an algorithm producing some randomized level, but as an AI simulation of the thought process of an actual level designer. A level design AI, if you want.
Definitely possible, and I'm not talking about machine learning ala Siri/Alexa here. I think the complexity of that would be about the same complexity as a capable RTS AI, for example.
The only reason this hasn't really been done yet is that usually, procedural generation is used for a much more narrow purpose. And, obviously, because getting such an AI right is very difficult, technically and performance-wise.
But this is a matter of time, only. Before Minecraft, nobody thought anything like it would be possible, either. Now it is the norm.
It is unwise to assume nothing more sophisticated would be possible.
Human design will always be superior to procedually generated design.
Until someone comes along and produces an algorithm doing all these things you just described, because
none of them are out of reach for procedural generation. If something can be done in theory, it will - eventually - be done in practice.
And until then, we'll just have to live with the occasional shitty procedural generation producing very doubtworthy results as well as those producing very good results - and most somewhere in-between. Just like manual generation.
Though for actual OP topic, I think that procedural stories (incl. characters, relations, arcs, etc.) are way more complex than any of the things I talked about above. Mostly because all of that requires way more creativity and cannot for a large part be "logically concluded" automatically.
We'll see awesome procedural levels way before we see awesome procedural stories.