Colonel, I think this is a fun topic, so I'll give it a shot.
As a precursor: I'm going to assume that "epic level" means having character levels in excess of 20. I'll also try and provide some of the reasoning behind my choices. Also, my reasoning is going to take things the characters did, and try to use a D&D framework to extrapolate the characters' power level.
Epic Level Characters
Gandalf the Gray (Fighter10/Wizard15). Gandalf did not do a lot in LoTR magic-wise, however I think a better way to guage his power is to determine what he
did do, and what he
was capable of, rather than what he wasn't. First of all, it should be noted that in Moria, he faced and defeated the Balrog single-handedly. If we accept that Balrog=Balor, then the MM tells us that a Balrog is CR18. So Gandalf fought and defeated a creature which
should take up 1/4 the resources of 4 18th-level characters...alone. Yes, he did die in the battle, but I also believe he was not fully rested at the time (and thus did not have 100% of his resources to draw on.) The conclusion? He is higher than 18th level, at the least.
It should also be noted that Gandalf showed a great deal of knowledge. He had high ranks in Knowledge (history), Knowledge (arcana), Knowledge (ring lore), and dozens of others, I'm sure. He most likely also had skill focus in many of these fields. He was proficient with swords and staves, and had a serious number of ranks sunk into Animal Handling and the Ride skill (note how he, and only he, was able to ride Shadowfax.) Ranks in diplomacy, intimidate, perform, craft (fireworks), sense motive, the list goes on and on. Even for a very intelligent wizard, the sheer mass of good skills he has is going to require a lot of levels...epic levels, in my opinion.
Arthur, King of the Britons (Fighter10/Barbarian10/Aristocrat5). As S'mon points out, there are legends of Arthur raging, as well as taking on hundreds of soldiers single-handedly. This means feats such as Dodge, Mobility, Spring Attack, Whirlwind Attack, Expertise, Cleave, Great Cleave, and possibly more. Many more feats than a low-level character might gain. Also, keep in mind that Arthur was the bearer of
Excalibur which is a very expensive weapon, possibly even a minor or major artifact. Looking at the Wealth Per Level table, we can see that only a very high level character could ever hope to procure such a weapon. End Result = Arthur had a lot of levels.
The Batman (Fighter5/Monk5/Rogue15). He doesn't have flashy powers or superhuman strength, but again it's important, I think, to look at what Batman is capable of, rather than what he isn't. The Batman is a capable martial artist, and can be seen in comics using abilities such as Flurry of Blows, Improved Unarmed Strike, and Deflect Arrows. He's also proficient in most weapons, and most likely has feats such as Lightning Reflexes, Iron Will, Great Fortitude, Weapon Focus (Unarmed Strike), Weapon Specialization (Unarmed Strike), Skill Focus (tumbling) among others.
However, in spite of his fighting abilities, the bulk of Batman's talent is taken up by skills. Batman is literally a jack of all trades, having high ranks in many knowledge skills (he must have taken the Cosmopolitan feat or something similar) balance, tumble, jump, hide, spot, listen, sense motive, move silently and others. He also often displays such rogue abilities as evasion, improved evasion, and defensive roll. In the end, he may not have godlike powers, but the sheer number of things he can do incredibly well demands epic levels.
Non-Epic Level Characters
Superman (Expert15). I don't see Superman's powers and abilities coming from training, or gaining power. Instead, I'd say that Superman is a human with the "Kryptonian" template. His levels, as I see it, have been earned while in the Clark Kent persona, with feats such as Weapon Focus (Eye Beams), Improved Unarmed Strike, and Skill Focus (Photography) and ranks in Profession (journalist) and Profession (copywriter).
On a side note, Superman could probably wipe the floor with a lot of epic-level characters (the "Kryptonian" Template is a munchkin dream

) but as far as levels go, he just doesn't have that many. And we're discussing levels here, which is not always the same as power level.
Okay, this is too long as it is, but that's my take on a few. Thanks for the topic, Colonel.
[Edit] typos... [/edit]