What is it that separates an RPG from other types of games? Please be warned that this is my own opinion on the subject. Other writers, many of them with much more education and experience than myself, have tried to tackle this with limited success.
Roleplaying happens when players go beyond the concept of "position identification" (i.e "This is my playing piece" becomes "This is my guy"). Roleplaying is encouraged when this works to the player's advantage. For example, Monpoly isn't an RPG because imagining yourself in the place of a top hat or shoe does not give you an advantage in the game.
The original Dungeons & Dragons game became one of the first games to offer this kind of advantage. Unlike many other wargames available at the time, D&D gave each player control of a single character, rather than a squad or army. And there's also the fact that first level sucked.
I really discovered that last for myself rather recently at the hands of OSRIC. My friend Fishgod had discovered this, dug out an old D&D module, and tried to run it for my gaming group. There was only one survivor. Mostly because we expected the rules to be more forgiving, like more modern games.
On reflection, it was this unforgiving nature that led to roleplaying in the first place. When you've got a visibly non-zero chance to enter play with only 1 hit point, you don't charge up to things with your sword. You get creative. You distract your opponents with changes to the environment. You lead them into the dungeon's traps. By visualizing the situation and putting yourself in your character's shoes, your character's survivability increased dramatically, making it more likely that you'll reach second level, at which point things get slightly less sucky.
Modern roleplayers (including some in my group) have complained that there is little room for roleplaying in classic D&D. The alignment system was not yet fully formed, so there's no real support for characterization and drama. Every adventure published for the system is a dungeon full of monsters to be killed.
By my definition, most of the video and computer games that are labeled as RPGs are not RPGs. They remove the player's ability to improvise solutions, reducing the game to the combat simulation that modern roleplayers decry. A well written story makes the game much more fun, certainly, but it doesn't really replace the flexibility of making your own decisions.
A couple of entertaining examples of what is possible when a person (as opposed to a computer) is mediating the action:
For those who have been following the Actual Play thread I have on wonderfulwizardofoz.net, I give you Corbin. In his first adventure, he managed to extend a war that otherwise would have been ended. Rather than tell him his action failed, and that his actions would continue to fail until he convinced the two sides to interact peacably, I allowed his actions to succeed and to let him deal with the consequences of his actions. It will be interesting to see him win over Ozma after that sort of incident.
Last night, Fishgod got us to try Paranoia. As a comedy game, one of it's many schticks that the characters are issued useless items and highly experimental items and are ordered to find uses for them. My character was issued a freeze-dried bagel and another character was issued a briefcase full of expanding monomolecular razorwire. After several characters fell victim to the razorwire, my character got creative and devised a shield made of the densest substance known to man: A freeze dried bagel. A computer would have to have planned rather far ahead to expect that move in order to allow it to work. Fishgod, seeing that it enhanced the fun of the game, allowed the unorthodox defense to take place and much fun was had by all.