Cryomancer
Arcane
I always thought leveling systems created issues like this. See, the original stories (myth, legend, folklore, pulp fiction, etc) that inspired games with level systems (i.e. D&D) were never written with leveling in mind. Leveling was added to give players the sense of earned progression. When you then try to apply leveling to worlds that were never created with it in mind, then it falls apart. I don't know if there's ever anyway to have leveling make sense with any world, even if the world is made with it in mind. I think it's too much of an abstraction.
In fact, I don't think horizontal advancement is present very much in the old stories either. e.g. the Greek demigod Heracles starts out with super strength, but he doesn't become stronger or develop additional powers. He gains a few items like the hide of Nemean lion, but otherwise he seems to maintain the same power level across the various monsters he fights. Most progression that I can think of in the old tales has to do with social advancement, such as Arthur becoming king of Camelot. Anyone have a better analysis?
IF you think in classes like "professions", it makes more sense. An lv 1 magic user is a guy which learned how to use spells recently and can only do very limited and weak magic, just a tiny bit better than a lv 0 commoner. An high level caster in other hands can do much more since he learned much more and got much more power.
That said, you can't compare Heracles with an advenurer in D&D; Heracles if was an AD&D char would probably be at least lv 25 and have godlike STR(24/25)