What Lurker said has already been implemented in other games (specifically in D&D games). A specific example would be chapter of the Hordes of the Underdark expansion for Neverwinter Nights. Exactly as Lurker described (I'm even suspecting he drew that idea from D&D), a door is locked wherein you should guess the next number of a sequence. The options include the possible answers and an intelligence stat check. Since my character was a wizard I had the option to breeze through it however I've been hacking and slashing so much that I needed a break and solved all the door puzzles manually.
Many suggestions here remind me of a lot of classic pc Rpg games. And I'm not even a fanatic on RPGs there are many I've missed like Fable, Gothic 1, Dungeon siege 1... Even my suggestions for the toolset are staple features shared by many (to the point that one can read it and say "duh! generic toolset").
