It's not about illusion of choice, it's about choosing what kind of builds you want to proceed through the game with. Your choice begins at character creation. Whatever character you build will likely always bee-line their chosen skills and deal with the game via those criteria. When you have a party of characters you are merely free to choose which form of progress you want to make at that particular time: Shall I bash the door down with my fighter or lock-pick the door with my rogue or cast a spell to unlock the door with my mage.
Whether playing with one character or as a party the player will usually tend towards the same routines for all similar encounters: I'll always let the rogue unlock the door, or I'll always chose the bashing route or I'll always cast the spell. Its no illusion, you are still choosing to progress the game however you want to with each different character offering different flavours.
Take conversational skill checks, for example, whether you have one party member or ten and the dialogue options are:
Bluff
Intimidate
Persuade
Bribe
Diplomacy
Attack
Then you can still only make one choice. And the choice you make will reflect the other roleplaying aspects of the game, such as alignment, cash-flow, XP gain, etc.
The choice you make in an RPG is very much dependent on what you start out wanting to play, and then proceeding to play that way. The nature of choice in a Choose Your Own Adventure is one where it doesn't matter who you start as, you simply take whatever the rolls give you as you progress and that determines how you play.
A good RPG will have so many character options that even within just one class you can have literally dozens of different starting builds which will proceed to provide you with a different game, no matter how many people you take with you. A dungeon crawler where you take 10 fighters is a completely different game to a dungeon crawler where you take 10 mages. And they are both different games to if you took 10 completely different classes, and this will be a different game to one with the same 10 completely different classes but all built differently.
You seem hung up on the notion that a skill check alone should somehow completely alter the game in some dramatic way, when that's not the point of a computer game, the point of a computer game is to work out how to beat it, nothing more, nothing less. Everything else is just flavour. In computer game role playing people expect to be able to see the whole game the first time they play it, because cRPGs are traditionally epic and long affairs and replayability isn't the primary objective, and when replayability is the objective it's traditionally via a variety of character builds rather than a variety of narrative forks, because narrative forks are an anti-thesis to the notion of epic exploration and seeing the whole game. Though only seeing 90% of the game is also fine and even preferable, because that adds just the right amount of choice to make it not feel entirely linear.
A cRPG with strong character build variety but only 10% non-linearity of plot/quests actually provides more in-game choice and variety than a game like Age of Decadence which simply presents a dozen linear stories interwoven into one short game, like a CYOA.
The general idea of a cRPG isn't to fail-state you based on a failed skill check, the general idea of a cRPG is to enable you to learn how to make a build work and to experience the same game from a different points of view/play-styles. No cRPG has ever been primarily about constantly choosing the green door in one play through and then constantly choosing the blue door in another play through.
You talk about Temple of Elemental Evil and how you'd like it if the game had more non-combat skill checks... but why? You never said why... You claim it would make the game better somehow, but why would it make the game better? It's perfectly fine as it is isn't it? I'm sure the game could be argued to be 'better' if it had a wider variety of weaponry, or if it had a wider variety of monsters, or a wider variety of explorable locations, but you think more skill checks are important for some reason?