He did mention Minecraft in the OP.
What I don't see a lot of is a dynamic / procedural / random adventure. That is, not just the dungeon is constructed randomly, but the characters and plot too.
Imagine random generation of a dungeon. Why couldn't you randomly generate a character in the same way? Define his basic personality attributes at the start, decide what his job is based on where he is and those attributes and who else is around. When you ask him questions, probably by asking keywords, the game decides based on the random seed and his Gossip, Ancient History, etc. knowldge-type stats, and where he is (a lone farmer knows less about current events than a bartender in a big city), to determine if he knows various types of info. For example, you could have info on the King of Examplia. Types of info would be Basic (he's the king, dontcha know, there are two princes), Specific (this is the politics of the king, this is what he looks like), Secret (rumor has it the king has an aluminum chamber-pot studded with yellow diamonds), Dangerous (there's a band of rebels trying to sieze the throne). Each info type will have a True, False, and Vague variant. Based on how much the person likes you, and his Gregariousness, and how much you bribe him, he might give you different information that he knows. Dangerous info would be very difficult to get. And it's not a matter of just bribing him over and over like Morrowind. He needs to like you, trust you, AND maybe need a bribe.
And the NPC should ask you questions. If you choose to answer truthfully, he gains that info. If you answer vaguely, he gains that info. Same with lies. If you haven't come across the truth yet, you can't know the truth, same with vague info. But if you have Truth you can answer truth of vague. You can always answer with a lie but based on your lying skill the NPC might think it's a lie or the truth. Lying to people makes them like you less. Lying to children, if they don't catch you, entertains them and makes them like you more (fairy tales, etc). Sometimes the NPC may think you're lying when you're telling the truth, and respond appropriately. Any info you give adds to what the NPC knows.
(This is sort of like the Daggerfall keyword conversations, except that you store a couple bytes per item instead of one on-off bit per item or however they programmed it. It's possible they just had several dozen "Conversation types" and some of those were for specific NPCS and some for every random person).