As for skill checks, TES games never had them for dialogue, so are they not RPGs now?
The distinction is that in RPGs you are intended to feel a part of the story and world, that you take on the role of your character rather than just playing it like a racing game or a FPS where you're just being you playing a game. This means yes, more games are RPGs than will be labeled RPGs. Also your definition of complex is very limited, Thief and Bioshock were more complex than TES games because of how you played the game and the ways the game challenged you, and not because a complex formula calculated the amount of damage you dealt with your weapon. You had a large variety of tools, but you had to use them wisely in ways appropriate for the situations. This can't really be said of TES, where I could use on simply strategy - even one ability almost exclusively - to defeat everything. I had a choice in what color and shape that one trick wonder was, I could even switch between them if I felt like it, but regardless combat was very dull.
For the dialogue system, ff you were trying to bribe somebody, this depended largely on your characters Speech Craft skill...it was the easiest form of raising "Disposition" but it also cost you money, and could backfire. A more complex RPG would also have the NPCs morals taken into account, and the
perfect role playing game would then inform you of what their likely moral outlook was, based on your intelligence/speechcraft. Obviously you can sometimes infer that because of the character (shady guy in a back alley) but sometimes it's harder (a corrupt noble). And that's what we'll never be able to do in Skyrim. It didn't work that way in Morrowind or Oblivion, but it easily could have within the system. They certainly hadn't perfected dialogue outcomes, but it's something you only can do with Attributes to give a baseline probability.
I just have trouble calling games role playing simply because they intend for you to feel a part of the story and world. A racing game could easily do that by saying you are Sam "Speedy" Gonzalez, and you need to compete in underground drag races to win enough money to pay ransom for your kidnapped sister. But it's not a role playing game. Even if you had the option of instead spending your winnings on a gun and bribing informants, ultimately tracking down and fighting the kidnappers, (which introduces complexity, and gives you multiple ways of resolving the story) it is still not an RPG. Until your specific version of Speedy is different from the given archetype, not just in the choices he's made but in the
ability to make those choices, it's not an RPG. Now, if you can choose for Speedy to drive Hondas better than Subarus, or use pistols better than shotguns, that is a role playing game. And to further complicate, it would help if he had Attributes such as Speed and Strength (which would then determine how fast he could run vs. how hard he can hit in a fist fight), rather than having every Speedy character run the same speed and hit with the same strength.
On the flip side, let's say you are playing Elf Quest, or Elf Quest II: The Re-Wizarding, and you are given a mission to kill some orc. Now, we'll pretend for this scenario that you cannot talk your way out of it, you have to kill him. An RPG doesn't care what method you use to kill this orc. You can use an Axe, a Dagger, a Spell. But you, as a character, are more likely to kill the orc with a weapon that you are proficient with. This engenders certain traits on your character. If you choose to use a dagger (because that's what you have the highest skill in) you will probably have to sneak up on him, because it's hard to penetrate armor with just a dagger in a straight up melee fight. The game has to account for this, usually by giving a bonus for sneak damage/armor penetration when using a knife, which is usually weaker than a sword or other large weapon (based on anecdotal evidence as well as leverage/mass) and because sneaking a knifing rely on similar attributes, such as Agility, (for accuracy in strikes and balance when sneaking) rather than the Strength you would use to wield a sword or axe with enough force to penetrate armor. This is the type of complexity an RPG should seek to have.
It's almost not so much choice in action as it is choice in character design. That's why I also don't think characters necessarily need to have "growth" in an RPG. You can start the game as powerful as you will ever be, but your character will be powerful in different ways than another, such as starting as a master swordsman vs a master archer. Of course the growth part adds fun and a "reward" mechanic, but it's not strictly necessary for an RPG.
TL; DR - RPGs aren't necessarily about choice. Your character will always have a better time of doing things in a way which you have predetermined. You have given a blank slate character the "role" of swordsman, archer, mage, and you then have to "play" that role. You can certainly use the other options, but your success will suffer for not adhering to the template you originally laid out. And I like that.
They also have stats, skills and perks btw. You can specialize in magic, sword fighting or alchemy and put points to each. There's also things like persuasion or threatening in The Witcher 2 that you can practice by using. There's also a similar mechanic in The Witcher but its been ages since I last played it and cant remember exactly what it was like. They both still have a lot of stats and stat checks though.
And that's what I was wondering, and that certainly does push it into the realm of RPG. If you focus on melee to the detriment of magic, you play the slightly altered role of Geralt, and later in the game you will have to mold your play style to those decisions. And I know from various reviews that it certainly is complex, probably more so than Oblivion in Morrowind in terms of possible outcomes. However, it would always be more complex if you had Attributes which are then variable, so that each version of Geralt is given different rates for success in a given outcome, such as deciding to run away vs. deciding to fight. You can always make that choice in terms of the game (which option is more difficult, which is more fun) but it comes down to player skill, how well you can maneuver your character and how well you've learned the combat system. In a more complex RPG, the character's Attributes and Skills would largely decide what action you take for the best result. It's just another layer of complexity on top of immediate choice and character skill.