All RPGs should be CRPGs (on the computer)!
And sure, some of those games gave you choices like that. Did all of them back then do so? Absolutely not. Ironic to your comments, there's actually a lot MORE choice in Borderlands compared to many "true" RPGs, as seen through the massive variety of choices between characters, equipment, and most of all in the skill trees. There are a hell of a lot of basic turn based RPGs that are utterly linear, most famously the Final Fantasy series.
And when you say "Diablo/Torchlight/Titan Quest where the answer is "more swords/spells" and the only real RPG elements are mechanical: levels, skill points, classes, etc.", I could just as easily say that the entirety of those game is fully RPG, and the only non-RPG element is the lack of choice. Hard to say a single arguably non-RPG element to game or genre = the whole game or genre being nearly invalidated as being an RPG.
In the end, if the thought here is that every RPG with a slightly different element or two of that of the original purist RPGs is not an RPG, alrighty. That's crazy to me, since there are variations within every genre of video game... ever... and they're still considered what they are. It's just being picky to a silly degree, imo.
Not exactly true. I've put hundreds of hours, possibly upwards of a thousand, into the Fallout FPS games, and while that's true of someone who's great at the game through early sections and on, it isn't true of later parts of the game. Try walking into Point Lookout or a Deathclaw nest with no skills built up and shitty stats. Good luck with that.
Of course, if you're playing on anything but hard or very hard mode, that's another story. The game is meant to be played at a higher difficulty once you've gotten accustomed to it. The lower levels are pretty easy and suited to new players.