Honestly, I'm not truly convinced that there is a problem. As you say, the 'problem' only appears as a significant setback with extreme tradeoffs. A character at PL10 who is at 16 attack/4 damage is not someone who is supposed to be going toe-to-toe with equivalent PL opponents.
People who are attack shifted should have a thematic reason for the shift. This theme should also indicate how they can rectify the situation.
Batman, for instance, is attack-shifted. He compensates by having a versatile selection of attacks with varied defenses. He also uses things like Set-up and Teamwork to benefit other heroes (such as those unfortunate bricks who are heavily damage-shifted but can't land a blow on an agile opponent).
That said, the suggestions you give for 'fixing' this don't seem to be good fixes for me. Both are variations of having your cake and eating it too by letting accurate attacks deal more damage. Autofire, for instance, means that putting 2 points into your attack is strictly better than putting 2 points into your damage: you are both 10% more likely to hit AND your attacks do 5% more damage.
Mutants & Masterminds is a comic book-inspired Super Hero game. Not all characters are supposed to be able to do everything. If you are being presented with a foe that your typical attacks can't hurt, consider what your favorite super hero does in his/her comic when confronted with that situation. Spider-man doesn't complain that it isn't fair his punches can't hurt Rhino, he uses his combat advantages to make him charge a power transformer or get stuck in a wall and webs him in place.
You don't need a mechanical 'fix' for a 'problem' that is intentionally built into the system. If you don't want to be faced with a situation where your character can't damage his foe, don't play a significantly attack-shifted character.
You can mathematically analyze mechanics to your hearts content, but if you are doing that at the expense of a fun game, you're missing the point.
Addendum: One thing that attack-shifted people have going for them is MultiAttack. I was reminded of this by this question. Multiattack adds +1pp/rank to the cost of an Effect, and allows you to do additional damage to a single target if you exceed their defense (+2 or +5, depending on how much you beat them by). You still have to be able to damage them with the attack (so you have to beat their Impervious threshold) to do so, but it addresses the tradeoff issue in much the same way as Autofire does. It also gives you a few other combat options (hitting multiple people for a minor attack penalty or giving an ally a Defense bonus).
Edit: In response to this being called a 'poor answer that dismisses the question', allow me to elaborate on my reasoning for being 'dismissive':
Attack is already cheaper to buy than Damage. Yes, if you just pump up your Str, you get melee attack and damage. But there's easier ways to buy your attack up. Most simply, you can get +2 attack / 1 pp by buying your attack as a skill (Close Combat: Unarmed) with a narrow focus. So an attack-shifted person who meets his caps can (and typically does) have more pp left over to buy things with.
The question points out that critical hits, which always hit, are a huge problem for attack shifted people: 1/20 hits, the defender will always lose anyway. The question indicates that this will be an auto-hit with +5 damage 1/20 times. Unfortunately, that's not right. This isn't always the case: critical hit must still exceed the targets Defense to get the +5 damage (or Alternate Effect). Of course, for a heavily damage-shifted character, one attack landing might be all they need.
The 'math' that is shown is overly simplified and the graphs are inconclusive. The graphs simply show numbers from -5 to +5, but don't indicate which direction the shifts go. They also assume two characters are simply standing and punching each other every round. Does this seem like something reasonable in a game?
The question, in my opinion, completely fails to demonstrate a real problem with the system. By narrowing it down to pure trade-offs and ignoring things like the fact that players typically have other party members assisting, the multitude of attack-boosting skills a teammate can have, and the many types of Effects that can render a character combat-ineffective without resorting to Damage, the question artificially narrows the system down to a single mechanic. The mechanic in question does have a bias, but the question neglects the many corrections for this bias which exist in the game.
The question seems to completely ignore any Effect other than damage. When simply hitting your target is enough (such as with a Chi attack resisted by Will - built as an Affliction with whatever penalties you like) being attack-shifted is purely better than being damage shifted.
Ultimately, the answer to this question is simple: work with your teammates to overcome your weakness. Watch an episode of Justice League where Batman and Superman work together. Watch Young Justice, and see what Robin does while Superboy is pummeling things. Watch Teen Titans and see why a young Nightwing is considered good enough to be on (and hell, LEAD) a team with a master of magic, a cyborg that can crush mountains, and an alien who can melt tanks from across the room.
When evaluating any system, you can't simply look at a single mechanic (in this case, trade-offs) - you have to consider the whole game.
Best Answer
This may not be as unlikely as you think
Preamble: Probability is Hard
So distributions like this are tricky, because a lot of people assume, wrongly, that they only need to calculate the odds of getting a distribution this good (or better), and then presume, based on the improbability of those odds, that it's evidence of tampering/cheating. But that's not quite right, and to demonstrate, I'm going to borrow an example Matt Parker used when he was assessing the odds that a speedrunner cheated an RNG mechanic in a video game.
In this example, we consider an experiment where someone flips a [presumed to be fair] coin 100 times. Then, after the experiment is concluded, a third party looks at the results, and notes that at one point during the experiment, there was a run of 12 flips which resulted in 10 Tails results and 2 Heads results. They then note that the odds of getting at least this many Tails results in a run of 12 flips is only about 1.9%, and conclude that this is improbable with a fair coin; therefore, they conclude, the person flipping a coin must have cheated, either by using an unfair coin, or by using some kind of technique to bias the results.
However, as Matt goes on to point out, you can't simply consider the odds that a run of 12 flips results in 10 (or more) Tails; you have to also consider the odds that, over the course of the entire experiment, you could get a run of 12 flips with an outcome this extreme. And as it turns out, those odds are actually about 88%. In other words, it's actually very likely, given enough trials of flipping coins, to get an individual run that's relatively improbable on its own.
So, in your case, the question we need to solve is not "how unlikely is it to get a run of d20 rolls this lucky in the course of a single night?", but rather "over the course of several sessions of a game, how unlikely is it for someone to get a run of d20 rolls that was at least this lucky?"
Let's do some math
So in your case, you've tracked 17 rolls from this player over the course of a single night, where the results were unusually high. Below are the odds of the two facts you've chosen to note:
One more fact I'm going to track:
So a brief sanity check we can perform on these odds, before we go further, is to note that none of these outcomes are terribly unlikely. The second condition happens more frequently than the odds of someone happening to roll a natural 20 on a d20 on any given roll, and we don't generally assume that any person who happens to roll a natural 20 is cheating based on that one roll. And there are a lot of improbable events that happen all the time that we generally would not think of as being evidence of cheating despite their absurdly low probability. As an example, I'll submit this combat log from a session my group had about a month ago, where on a 4d8 roll, our cleric rolled four ones, and then promptly rolled a natural 1 on her subsequent attack roll:
And, just so it doesn't go unstated: I can personally verify, as the DM and maintainer of the VTT these results were obtained upon, that these were fair results, despite the fact that the odds of this happening were about 0.00122% (or, 1 in 81,920).
But, I should also not leave unstated: that was a cherrypicked result from a long series of rolls over the course of a campaign that has run almost every week over two years. You could dig into any campaign and find individual runs that were at least as unlikely, perhaps even moreso.
Now, in your case, we don't have every single d20 roll to analyze; only the 17 from the session you chose to record. So we do have to make some educated guesses about, for example, how many sessions you've been in this campaign/game with this player, and how many d20 rolls they made in those other sessions. I'm going to assume that each session you've participated in has had a similar number of rolls (so, 17). We then have to ask, given the probabilities for each of the facts we're considering, how likely they are to have occurred at least once over X sessions.
Now, it's important to note that not all of these numbers are simultaneously relevant. It's much more likely that one column is the most relevant, depending on how exactly you think this player is cheating (i.e. are they fudging die rolls higher? Are they making up numbers and just happening to choose them to be high? Are they making up numbers, but only when failure would be really bad for them?).
What's relevant for our purposes is that if you've played only 6 sessions with this player, then regardless of which properties we think are relevant, the player has at least a 5% chance of achieving those results at least once off a fair set of dice. If you've played more sessions with them, those odds get a lot better. A 5% chance is low; but again, 5% chances happen all the time.
And this assumes that we only care about the average result, i.e. we assume their method of cheating is that the player has been systematically nudging their dice results upwards. If we think their method of cheating has been to (secretly) reroll low results, then the results they achieved actually have a 30% chance of happening legitimately.
Conclusion: The results you sampled do not prove cheating
To be clear, they don't prove innocence either. A 5% chance is pretty low, and if the player is cheating, these results would be consistent with what you'd expect given a player who either systematically fudges die results, or who just makes up numbers and biases them to be high enough to succeed.
But what I would say is that, if you plan to accuse a player of cheating in this game, I think this data would not be good evidence to support it. The odds that they're playing fairly are just too high. At best, it suggests a need to monitor their results and see if they continue to get lucky or if this was just a hot streak, and I think that to say the player is definitively cheating, they'd have to have odds lower than what's being shown here. If you collect more of their rolls, you'd be able to run a similar analysis with both sessions' data and narrow things down a bit, which might get closer to proving that they are or aren't cheating.