Ultima VII & VIII had some great puzzles, very complex ones, very creative ones, ones involving switches, invisible chests, secret passageways, translating languages, music patterns, a plethora of modes and methods producing the richest puzzles I've ever experienced in any game. I'd highly recommend such puzzles in SOTA! Thanks.
2nd that. Though being primarily a single player game and being RG I'm not terribly worried about it.
The problem I see it with inventing and implementing these sort of fun in-game puzzles as you mentioned is the internet. Yes, people have the option of not looking up answers to these complex puzzles but if there are rewards associated with it people will quickly enhance their understanding of the process. I'm not sure if we'll ever be able to go back to a place where we're all playing a game for the time and there are no outside sources to help our knowledge of the mechanics of the game, I'm sure the team will be able to develop some puzzles that are completely random and the answer cannot merely be looked up but nothing will be like finding the secret passage in the Minoc mines or the magic carpet.