Zeewolf: A problem here is that most definitions of the RPG-genre are opinions as well.
Feel free to give a better one then, and explain why it is better.
Navagon: Ideally, an RPG should be as fluid and seamless as possible. The mechanics of the pen and paper game exist only to give the game structure. This can be far more transparent in computer gaming.
Personally, I prefer levelling systems that reflect this - that increase your skills in any given area as and when you use them rather than requiring you to manually enter points, possibly even into skills you have yet to use. It seems to me to be a weakness of a genre that you can exploit the system like that.
A true RPG is simply one that is just that. A game where you play a role. Therefore character development, interaction with others and ultimately the effect you have through the choices you make are of paramount importance. Not making the mechanics as evident as possible. The more choices you have and the larger their impact, the more like a true RPG the game seems to me.
Deciding how to improve your character also gives you choices, and manybe important ones. Do you improve that skill that will help you bullshitting other characters into believing your lies or the one that lets you kill people quickly from afar? Or maybe the archeology skill that will let you decypher that old important-looking stone tablet in that temple? Choices and consequences.
The current trend is to try to hide as many data from the player as possible but that's mostly a lazy way to do things, because if you really want to give the player a lot of options you have to give him the mean to develop these options. It doesn't mean that you need to use a lot of obscure and confusing rules — D&D 2 is kind of a reference in that field — but you can make them all sensible and clearly available as in Fallout, where you can see right away how stats, traits and perks influence skills, all in one screen.
How exactly is it a weakness of the genre to give you options to develop your character? I'd very much define as a weakness a system where skill improve when being used, because while it sounds good on paper it leads to all sorts of abuse: keep casting a low level spell while walking to improve your magic skill, keep jumping around to improve your acrobatic skill, etc. It just makes the act of increasing skills and leveling up not only tedious — really, it sounds like work, the kind of stuff I do to be able to eat every day and buy games that I can play so I get a distraction from work — but also insignificant, because you increase it from very trivial actions. Leveling up and increasing your skills should be a reward for accomplishing important tasks. Bloodlines has a pretty nifty system where you unlock new skill levels by investing points into them and you get those points only by completing tasks, no matter how you did them, though completing special objectives could net you more points; this means you would get the same reward whether you decide to kill everyone in that enemy-infested warehouse or sneak past them.
Another way to deal with the skill increasing by use is to make it very slow, like in Jagged Alliance 2, but then it isn't a reliable way to improve your character since it takes so much time, more like once in a while you get a little bonus for performing well and mostly need to have your merc train in their free time, at the expense of doing something else — choices! Or you can abuse the system by having your merc run around while heavily loaded or repeatedly throw knives at crows, and no it isn't as fun as it sounds.