Randomness of elements required to succeed = bad.
Randomness of elements tied to exploration = good.
You definitely do not want to ever have progress blocked by bad use of RNG. Actual progress in the plot should generally be tied to player knowledge and skill, however the rewards of said progress are fair game. In fact, randomness in reward may even be better. The psychology of risk and reward is a funny thing but overall people respond better to an inconsistent reward than a guaranteed one. A player can get desensitized to a simple and predictable reward. "Go down the hall, open the chest that has 4 Potions. Fight. Oh, 3 Bats, that'll take 2 turns and net 36 EXP. Yay." But inconsistency keeps a player more engaged since they can't know what the reward is going to be ahead of time, thus it keeps a certain level of excitement. Even if most of the rewards are the same generic junk they'd be getting anyway, knowing that there is a chance it could be something extremely powerful - no matter how small the chance - still keeps some level of excitement.
Persona 4 does this almost perfectly. On the surface it's a very simple Turn-Based JRPG battle system - hit enemy weaknesses for more damage. The catch is that hitting a weakness also knocks the monster down, and if all of the monsters on the field are all in the "Down" status at the same time you can perform an "All Out Attack" to nuke the field. This is a cool way to clear mob encounters, but if the "All Out Attack" also ends the battle then it triggers a wonderful little thing called "Shuffle Time". After the battle an event triggers and the player is dealt 3-5 cards. These cards are all part of the Tarot set used throughout the game and the effects of each card varies from giving you a new Persona to use in battle, to restoring some HP and SP to the party, to modifying the amount of money and EXP you receive (increasing or decreasing). Then there are the super powerful effects, like giving your active Persona a permanent stat boost, evolving one of your active Persona's skills to one of the next tier skills, or flat out giving your active Persona a full Level Up. Normally you can only pick 1 card and that bonus can be pretty sweet, but sometimes the cards will be marked 1 More or 2 More which let you pick up extra cards and if you manage to pick up all of the cards you trigger the Sweep Bonus which guarantees Shuffle Time after your next battle. This turns each battle into a challenge to not only win, but to win in a way that triggers Shuffle Time. The possibility of Skill Up, Stat Up, and Level Up cards is way more exciting than just grinding fights normally and it's done in a way that still gives money and EXP to keep progressing even if you don't get any cool rewards. It makes each battle matter as even an easy encounter while back-tracking might still grant you a Level Up card if you're very lucky. To a lesser extent there is also the randomized dungeons and treasure chests, with each treasure chest having a chance to be a sparkly golden chest that contains special loot but which needs a Chest Key item to unlock...items which are most easily acquired through Shuffle Time.
Elder Scrolls V: Skyrim does this more for exploration purposes. Outside of the main questlines, many of the side quests use the Radiant Quest system which has the quest select a dungeon that the player has not discovered yet. Depending on how thorough the player is when traveling it can actually be very easy to find dungeons you never knew were there previously this way. This also helps the huge map the feel less empty since every single one of the hundreds of caves and abandoned forts and ruins can be the location for a quest rather than just something that's out there in case the player feels like walking in that direction. This is also done with some of the quest rewards granting random gear. Presumably this is done to give the player a cool item that makes them consider changing up their play style periodically to make use of the powerful new item they got. In practice this does not work that well since Perk points are limited so builds are mostly planned out from the start and any gear not fitting the Perks you were going for is useless. This is probably why Bethesda included ways to respec Perks in the DLC.
Mobile games like Granblue Fantasy and Fate/Grand Order also use that addictive mechanic known as the Gatcha Roll (see also: Large Ship Construction in Kantai Collection). These games have hundreds of playable units with distinctive designs and sometimes personalities (particularly Fate due to the amount of characters fleshed out in other parts of the franchise already). Obviously there needs to be a good way for the player to collect them that also encourages them to play daily. The Gatcha Roll fulfills this need in spades by letting players accumulate resources by fighting and completing quests that can be saved up and later spent to acquire new characters by a random roll. This works somewhat like a loot table with a roll to determine tier (1-5 Stars in Fate) followed by another roll to determine the reward to dish out from that tier. This can pretty much be guaranteed to get the player some solid mid-tier characters to clear quests and event challenges with the ever-present possibility of scoring a rare high-tier character which are highly coveted due to great stats, good skills, and usually amazing artwork. This method relies on a degree of player attachment and personal preference, like Fate series fan favorites Artoria and EMIYA being 5 Star and 4 Star respectively, so players will keep playing for a lucky chance to pull Artoria while having a decent chance to pull EMIYA eventually. The game is perfectly playable without either but the fact that most series fans will want them means that a "dangling the carrot" strategy works pretty well. I suspect this can work pretty well in other formats, but you'll need to 1. inform players about what the highest tier rewards are, and 2. actually make them care about getting them.
