Anyone play/check-out warhammer FRP 4ed? (Fantasy Flight Games Version).
They use a unique set of dice for task/combat resolution. No numbers, but hits, misses, boons, and banes. You build a dice pool based on ability used, ability score, training, stance, and luck then the DM adds dice to the pool based on difficulty, misfortune, active defenses, etc. then you roll the pool.
What is interesting is that you can get more misses than hits (a miss) but get more boons than banes (good results) and visa versa.
I think something along those lines would help. You don't need to eliminate the binary skill check (success or fail) but there should be another thing that is less digital/binary and more analog/sliding scale.
The analog/sliding result is what you look at for guidance in the narrative.
E.G.
Player: "I failed my dexterity check to sneak past the guard, but I did really well on the <analog scale>."
DM: "OK. The guard turns and looks at you as you kick a loose pebble, alerting him to your presence. You are still in the shadows and the guard is standing next to the burning brazier, light in his eyes. He says 'Made me jump Franco, you forget something?' The guard thinks you are someone named Franco. What do you do?"
Player: "I'll think I will Bluff. I am pretty good at it. I'll mutter 'yeah, good night' muffled with a cough and I wave at him as I walk awa, still in the shadows"
I like the WFRP dice so much I may use them for skill challenges. Its the sort of "revolutionary" idea D&D needs for its exploration pillar.
Perhaps a D&D version would be a simple "save" like 4th edition (beat a 10), but you add "points" to the point pool based on ability score, skill, situation, and the DM added penalties based on difficulty, defenses, etc. muych like the WFRP dice. You roll, and add the modifiers. <1 very bad, 1-5 bad, 6-10 inconvenient, 11-15 small advantage, 16-20 big advantage, >21 Awesomeness.
to take my dialogue above as an example, player adds a bonus for his dex, sneak skill, and the presence of shadows (along a wall, or at night eg). The DM subtracts the guards spot skill, his wis bonus, but adds a bonus due to the guard staring into the brazier to keep warm.
Dice are rolled and the player gets a 16, Big advantage. Despite the failed roll to sneak, DM give the player a chance to get away clean. In the example, he uses a bluff check.
If it was a 21, maybe the guard says "Hurry inside, they are waiting for you.". The PC was detected but the guard let him in anyway. seems like an effective success, but when the person whom the guard mistook the PC for shows up, the alarm will be raised.
If the result was a 12, perhaps the DM would have the guard shout, draw his sword, and threaten the PC (allowing the PC to turn and run) getting a good look at him (and putting the guard on alert for the rest of the night)
whereas a 7 might have the guard shout "halt" and interrogate the PC (more skill checks)
A 3 might lead to being arrested and interrogated
and less than a 1 might have the guard spin and hack the "assassin" , starting a combat.
All of the above was a failed skill check roll.
Similar things could be done on a successful check. The guard doesn't spot you, but the gate closes, another guard shows up, etc all the way to you succeed and you are able to move twice as fast, create a diversion, or spot the quarry you are after.
A simple version would be to make it binary as well (boon/bane) and rather than modifers to the roll, have advantage/disadvantage (but in this case, they are stackable so that 2 advantage plus 1 disadvantage = advantage)
So skill resolution results in
Succeed - Boon
Succeed - Bane
Fail - Boon
Fail - Bane
That may be enough "analog-like" smoothing to give a variety of results.
YMMV