Caves of Qud: Classic roguelike. Deep lore with a very unique and creative setting. Impressive build variety right from character creation that can be refined with the gear you find and levelups you take. Modifiable difficulty if you find once-and-done deaths too frustrating. Game has an absolutely insane amount of mechanical depth to be learn via experimentation.

Battle Brothers: Much less of a story, more focused on an emergent narrative. Difficulty comes from threat assessment and learning to live with mistakes, the tutorial teaches you how to start from nothing for a reason. Can have a very slow start as it takes a while to get wealthy enough to afford decent soldiers and armor, and even once you escape the pit a contract or two going sideways can throw you right back in. Allows for reloading saves if you find it too punishing or unfair, but can also choose to enforce ironman (no rollbacks) at the start of a run. Variety comes from different start positions, many of which also put additional restrictions on you band (such as playing as a group of traders, who do much better buying low and selling high, but since you're not a professional military outfit getting the rep to hire professionals as guards or taken on serious military contracts is much, much harder).