Ok, I was going to leave this be and go to sleep, perhaps address it in the morning, but I literally just got pulled back to the keyboard. Here goes:
A good definition should include criteria by which we can measure whether a certain object (in this case, a video game) fits within a certain category. In gaming, this problem is made difficult by the merging between categories and the vast variety of titles. Nonetheless, I've basically boiled my personal definition down to this:
The first criteria that differentiates an RPG from other genres is the presence of a coherent storyline that begins and terminates (whether at the game or in a sequel). Thus, multiplayer only shooters and sports games are immediately sieved out (they may have a 'setting' but are not primarily focused on telling a good tale). Some RPGs relegate storylines to second place behind gameplay (see Diablo-style games and MMORPGs), but they all have it.
The second criteria is a focus on identifying the player with a primary controlled character. Whether the character is created from scratch by the player (D&D, Bethesda etc), chosen from a variety of models (Jade Empire, Borderlands, Diablo), or handed over pre-conceived and modeled (the Witcher, many JRPGs), the player is always asked to 'be' that character in a certain sense. This is true even when the game is party based (NWN2, DA:O, JRPGs). This filters out RTSs (which put you in the role of a commander, not an in-game unit. You are yourself, not a creation). So far so easy.
The third and most important criteria is that an RPG must have a sense of progression for the main character. This is what sets apart RPGs from two closely related genres: story-based shooters and adventure games. Progression can usually be found in two forms: of skills (nearly universal) and of character (not always present). RPGs may not need much freedom in terms of storyline, but it must give the player some choice when it comes to character progression (it is impossible to have a completely non-linear storyline in any game, at best a degree of storyline branching can be included but this never comes close to a true make-you-own-story model). This freedom of choice serves to reinforce the bond between the player and the character, leading to greater emotional investment and 'role-playing'. Shooters traditionally have neither skill or character progression, although more and more have a bit of the former and a touch of the latter. Critically, however, progression in both these areas in shooters is almost always tightly-scripted and pre-determined. In adventure games, skill progression is usually relegated to the granting of new abilities for the solving of puzzles and is heavily predetermined and all character progression is pre-scripted into the plot. Thus, they cannot be RPGs.
This brings us to the issue of combat. A possible fourth criteria might be the presence of a system by which skills, directly or indirectly, progress a plot. Note hear that when I say skills I'm trying to refrain from using a restrictive sense of the word. In Mass Effect, skill means abilities and crosshair accuracy, in Diablo it meant new spells and abilities. In Pokemon (which entirely fits my definition of an RPG), learning new skills is equivalent to catching new Pokemon and using their abilities in battle. I don't want to make this criteria too rigid because a skill-testing system can come in many forms. Importantly, however, combat (or whatever system is used) shouldn't only be for the sake of progressing the plot but equally for the sake of testing and using new skills. This again separates RPGs from shooters and adventure games. I say this because skills should be earned with the purpose of frequent usage and enjoyment in mind, not utility for getting through the game. If this sounds controversial, it's because it is, you might disagree.
Anyhow, that wraps up my definition. Have fun kids, I'm hitting the hay.