Well I'll start by addressing your issue. One of my pet peeves about leveling up is that we are led to believe that growing up your character reached a certain degree of development in some twenty odd years, and then goes on to become a high-fantasy, world-saving, swashbuckling hero over a very short time span. I think Fable had an interesting approach to solving this problem in theory, but fell a little short in execution. Another RPG that solves the issue well, I think for the scope of the game is EVE Online, were in addition to acquiring XP, you also need to spend TIME advancing your skill. Depending on the setting, this may or may not work for you.
One solution is the "race scenario", which would work well for any high-fantasy type story-line. You have a certain amount of time to reach a given objective before a key event occurs. You then have to chose between leveling up your character and uncovering clues as to what and where the key event is going to take place, and what skills and equipment might be good to have. That way you can chose how well prepared you want to be for any confrontation, and whether you want to spend your time relying on brute force (be the biggest, baddest swordsman there is) or strategy (find out that your would-be opponent is vulnerable to fire, and bring a fiery weapon).
One solution is the "race scenario", which would work well for any high-fantasy type story-line. You have a certain amount of time to reach a given objective before a key event occurs. You then have to chose between leveling up your character and uncovering clues as to what and where the key event is going to take place, and what skills and equipment might be good to have. That way you can chose how well prepared you want to be for any confrontation, and whether you want to spend your time relying on brute force (be the biggest, baddest swordsman there is) or strategy (find out that your would-be opponent is vulnerable to fire, and bring a fiery weapon).