Fate Core is a definite candidate
If you're looking more at telling the story of people trapped in this world, rather than a combat simulator, Fate Core is worth looking at. Let's look at your criteria.
PC's should fail often.
This is clearly a matter of how you set up your opposition - if you give easy opposition, your PCs will succeed most of the time.
However, Fate Core goes out of its way to emphasize that failure should be a continuation of the story, not the end of it. Concessions in Conflicts exist to let one side back down, losing the "point" of the Conflict, but avoiding the worst parts of their fate (pun intended).
Additionally, the mechanic of Fate Points works best when players fail on a regular basis - in this situation, players know that spending Fate Points to succeed in one scene makes it likely that they'll "lose" in another. These tough choices drive really good Fate games.
Fails should be treated interesting and moving things forward
Absolutely. Fate Core is very explicit that you should only roll when you have an interesting idea for both failure and success. Failure can explicitly be interpreted as "success at a cost" to keep things moving where there's no really interesting failure state. This can require a certain amount of imagination on the part of the GM, however.
Again, we can look at Concessions as an example of this. A Concession mechanically gives the players a "get out of dodge" card that can be used, allowing them to avoid the worst of what happens while still "losing" the encounter. "The messenger got away, but at least we lived!"
In a recent game I ran, players ran into some enemies outside of their ability to take on (at least in that quantity). They Conceded the fight - resulting in their escape, but the enemies now knew who they were (and could use that info against them).
Even if not Conceding, it's probably worth noting that there is no situation where Fate says "your character is dead." The worst it says is "your character is Taken Out, and whoever did that decides what that means." It could mean "dead", but that's up to the GM.
The default assumption in Fate Core is that failure means that the game continues in an interesting way, and doesn't just end.
Avoiding frequent fails is possible if using advantages, tactics, surroundings and clever tricks.
Absolutely. Fate allows not only the usage of Fate Points to help out when you really, really don't want to fail, but through the Create Advantage action allows for almost any kind of maneuvering the PCs can think of. I've had PCs do everything from disarm enemies, to tripping them, to throwing doors on top of them, to holding them down with blankets, to finding weak spots, to....
The only thing Fate doesn't do as well is the type of "tactical wargame" stuff you might find in something like GURPS or Savage Worlds. It can still do "tactical", but that's going to feel more like how tactics would work in a book, or a movie, than a tactical minis wargame.
A wide range of results: crit fail, fail, partial success, success, crit success (just an example).
A standard roll comes with the following possibilities:
Success With Style
Minor Success/Success at a Minor Cost
Failure/Success at a Cost
If it's an opposed roll, the opponent can also Succeed with Style, effectively adding a fifth case.
Even one success matters (one hit could change the course of a fight)
This one is a bit more iffy. Fate Conflicts (which could be mental or social or anything, not just 'combat') are based on stress. It's kind of hard to one-hit a PC (or major NPC) in Fate. However, a single hit can do a ton of 'stress' (which isn't damage), as well as inflicting one or more Consequences (which can be any kind of injury, etc.). Additionally, Consequences get a free "invocation", which allows them to be used for a bonus, creating a mini-death spiral.
So a single hit (especially if it's built up with maneuvering beforehand, or usage of Fate Points) can have devastating results. But it's not likely to Take Out an opponent in a single shot.
On the other hand, it's rare for an opponent to survive more than 3 or maybe 4 successful attacks, even if they're just "plinks". There's not really a lot of cases where you'll be whittling away hit points round after round.
Supporting the Themes
This one wasn't listed as a requirement, but it's something where Fate Core could help out.
One thing you can do in a Fate game is set up a campaign or setting-level "Aspect". For instance, you could set up an aspect of Absurdist Satire. This will do two things for you, mechanically.
First, it gives the option to "Compel". This is the ability to offer players a Fate Point in exchange for something going wrong - and if they reject it, they have to pay you a Fate Point. "Because this is an Absurdist Satire, it would make sense that the guy with the part you need will only give it to you if you can provide a form XKR-132-B. This goes wrong when you realize that you haven't seen a scrap of paper in a hundred miles."
Players can also propose their own Compels, either against themselves (gaining a Fate Point if you think it's a good Compel), or even against NPCs (costing them a Fate Point).
The other thing that a setting-level aspect gives players is the ability to "invoke" it (using a Fate Point) by describing what happens and paying a Fate Point in exchange for a bonus. This is done during the process of resolving the action, and so it adds to what's happening.
"Yeah, it looks like the guy's going to hit me, but it's an Absurdist Comedy, and so his bat falls apart because it was made by the lowest bidder."
Why You Shouldn't Use Fate
I think any good recommendation should include reasons why the recommendation would be inappropriate.
- Fate's not a traditional game. Figuring out how it works can take a while for some people that are heavily into more traditional games.
- Fate's a "fiction first" game - it expects you to have a good idea of what's going on, and then to consult in when you need to figure something out. If you're looking for a game to model every bit of the world, it won't really do that. It gives you tools.
- Forget zero to hero. Fate has a very flat advancement curve.
- Requires everyone to be on the same page. Fate is a very, very bad game for dealing with disruptive players. It assumes everyone will act like adults. Someone wanting to be a jerk will definitely find it easy to do so.
- No one-hits. This is either a positive or a negative, however it kind of maybe goes against the "single hits matter" requirement, so I'm listing it here.
- Fate kind of requires a GM to put the screws to the players, especially if you want to drive it to having any kind of grit. I think it's kind of intended to do that, but if you run it "neutrally", it's very easy for it to become a series of successes. The trick is remembering that the PCs have plenty of power to get out of the worst of the situations.