To me, the thing that makes a Mary Sue or Gary Stu what they are isn't their objective power level, but the fact that whatever their powers are, it's always the perfect answer to whatever problems they come across in the story and prevents them from ever failing, losing face or not achieving their goals and being universally feared or admired. That's how you can have Sues and Stus in stories that have no super-powers at all, they're just in a high school or similar (ie. character has rainbow dyed hair and collects cacti. Every attractive, cool and nice person they meet will be in awe of this amazing hair and want to be their friend and will thing collecting cacti makes them the coolest and most endearing, and anyone who tells them to change their hair or says collecting cacti is boring will immediately be proven wrong and have something bad happen to them and it'll turn out they were just jealous.)
My favourite example of super-powers and Gary Stus is the villain Zehir from Legend of Korra. He's a skilled martial artist who has been in prison for decades. Suddenly he gets airbending powers and within weeks is the best airbender in the world, able to use super-advanced forgotten techniques, defeat the world's greatest airbending master, Tenzin, and the Avatar, who has the completely broken ability to wield all four elements due to being effectively a demigod. Zehir's power level is higher than the big final boss of the Avatar the Last Airbender series, the Firelord, a super-experienced bender, during the eclipse, a magical event that boosted his powers extra high. Every problem Zehir gets into, the narrative contrives in such a way that he wins, even though it doesn't make sense and requires the other characters to perform poorly and not use their abilities to the level the audience knows they can, or for him to suddenly pull a new power out of nowhere.
One of the reasons people love Spider-man so much is that while Spidey is an incredibly powerful hero; able to lift several tons, super-smart and able to make gadgets and tools, really fast and agile, can climb walls and shoot and swing from webs and has a danger-sense, these powers don't solve all his problems easily. He's still vulnerable to bullets, he's not omniscient, can't be in two-places at once and he's highly honourable and dutiful, so will always put protecting and saving people first, which is a very exploitable weakness. He also has a lot of personal problems in his real life, like struggling to pay rent and maintain a career and relationships on top of his hero duties. He has great powers, but they don't perfectly happen to always work as the exact solutions to his problems without a struggle, and they don't make him immune to losing things he cares about, looking foolish or being disliked or misunderstood.