I like how Pathfinder 2E does it. A 20 brings your result one tier higher. A 1 brings your result one tier lower. With a high enough base expertise, you can still succeed when rolling a 1, just not as awesome as you normally are. And a 20 isn't a guarantee against really strong foes.
This. Plus, if you beat the DC by 10 or more, you get a Critical Success or if you fail by 10 or more you get a Critical Failure, regardless of the dice roll.
And for opposed skill checks only the player/NPC taking the action rolls a d20, and that's compared against the opposing skill DC (10 + ranks). This streamlines play and reduces random variability.
So in the example here, only the rogue would have rolled the natural 1 and added 26 for a 27. The paladin's Perception DC would be 16, so the Rogue beat it by 11 and it'd normally be a Critical Success. But since it was a natural 1, the Critical Success is reduced to a Success. They still succeeded at deception, but not quite as well as they could have.
In epic scaled games, I work around this with a "reroll at -20". So the rogue in this case would have had about a 25% chance to recover on a DC10 check.
I also always include an in-game explanation. In this case, I would have made it a huge flashy "boon of insight" from the Paladin's deity.
Then it's all the more fun if the rogue actually manages the re-roll. "Dude, I even tricked your god!"
I would also RP right into it. "A voice from on high intones 'I dunno, seems legit, to me.'"
Similarly if the rogue actually fails:
"A voice from on high intones 'Seriously, you need to stop falling for this crap. I'm going to send you an amulet of insight or something. What's your next stop?'"
This is why my house rule is nat 20 or 1 gets a second roll to determine the degree of the crit. A 1 followed by another 1 is your true fall on your face odds.
Critical skill failure is relative to the situation, you don't chop your arm off everytime you critically miss in combat. Although if it makes sense for the specific situation, chopping your arm off might be on the table sometimes for a critical miss in combat. Same sort of thing works for skills. It would only be the worst reasonable result that comes to mind. Not that all of a sudden the worst possible thing ever happens completely out of the blue.
I like the idea of a critical role needing another roll to see just how critical it was. That way something crazy can always happen, but it doesn’t need to be a certain doom either.
I've been trying to include failure techniques from DungeonWorld's suddenly ogres in my game. It proposes a few neat ideas for consequences of failure that are broadly applicable to many RPG systems.
Eg, in the example above, maybe the Rogue (truthfully or not) blabs that their source was [ancient evil tome forbidden by the paladin's order]. Now the complication is not that the Paladin disbelieves the rogue's claim, but that they might question the rogue's true intentions.
Edit: Or in the example given about landing a plane. An experienced pilot won't crash 1/20 times, but what if Air Traffic Control did a bad job managing things today? It will take 1h for the plane to be assigned to a gate, but you need to catch the train to Borovia in 1h15.
An award winning surgeon rolls a 1 while giving a routine lecture? The presentation is so fucking boring that half the students fall asleep. Now the surgeon has to deal with the extra office hours of students who don't understand this part of the curriculum.
Yeah, I really like the "success with complications" category (Fate system does something like this, too) to keep things moving when a bad roll would otherwise make 1-in-a-million tragedy happen.
Doubly so if that bad roll would be a session- or campaign-ender.