1) Mr Majestic:
Well, when Superman disappeared and Majestic appeared (and at the same time a time vortex was threatening to destroy metropolis), Eradicator and Steel (John Irons, although at the time it was his duaghter who was Steel) did not trust Majestic. Infact the only person who did was Lois for some reason.
They even thought he was responsible for the whole Time Storm, and because he was warning them to not do anything they decided to get him out of the way.
How did they do that?
Well, they imprisoned him in the ....you guessed it ....the Phantom Zone.
Majestic was stuck there, unable to do ANYTHING, until Lois decided to free him by turning it off.
Thus, we have Mr Majestic completely trapped within the Phantom Zone ....a dimensional prison that has been used to imprison everything from White Martians to you name it. Helpless.!
2) SuperBoy Prime
When SBP showed up and started wreaking havoc they decided to do something similar.
Actually the exact same thing.
They imprisoned him within the Phantom Zone!
What happened?
The kid PUNCHED his way out! Literally pummeled his way out of the Phantom Zone, and if I remember correctly it only took a couple of punches at that.
On top of this the kid was imprisoned within the Speed Force.
What happened?
Kid got out.
Conclusion:
Majestros is a supreme character.
In several of his portrayals he has been written as basically being Pre-Crisis Superman in many ways (without the sneezing away Galaxies aspects).
On top of this he has a keen mind (almost pre-crisis level genius, and somewhat comparable to the intellect of All-Star Superman).
And his abilities are just insane (eg planet-moving, sun shearing, surviving to the end of time).
HOWEVER, on a purely PHYSICAL level, Superboy Prime is his superior.
The kid was PUNCHING out of places that had Majestros totally helpless (and requiring the assistance of Lois to escape).
Anyways, Majestros can DEFINITELY defeat Superboy Prime ......that is a 100% given.
The only thing is he would require prep to do so.
A sudden bumping into each other, followed by a physical confrontation, would have Superboy Prime defeating Majestros.
However have Majestros have prep time, and access to Kherubrim warware, and the situation can be quite different.
Winner:
Without prep .....Superboy Prime with the greatest of ease.
With prep .....Majestros with the greatest of ease.
PS: Someone was saying that Majestros was not all that because Spartan beat him.
I have that comic where Spartan beats Majestros.
Majestros tears apart many spartans before the 'real' one comes up ....you know, the one that has absorbed the Void.
That Spartan is a killer .....there is a reason he survived to the end of time and became GOD!
There are not many characters that can defeat THAT Spartan, and thus there is no shame at all falling before him.
Although I'm sure many here probably think Wolverine could defeat him (and probably think it is the same Spartan that was ONLY a cyborg, yet now he is much much MUCH more than that after absorbing Void ......he could take out Wolverine's entire adamantium skeleton either through pure physical force, or by fraying away all his skin with super-intense heat, or simply by teleporting the entire skeleton to a nearby solar system).
When Spartan was a cyborg and nothing else then he was a chump .....the way he is now makes him a totally different ape.