Comment by kibwen

Perhaps modern AAA games have become so handholdy that any game that shuts up long enough to allow the player to experience a sense of genuine exploration and wonder counts as a puzzle game, in which case I'd recommend the rich genre of indie Kings Field-likes, e.g. Lunacid. A bit further out would be something like Moonring (Ultima-like) or Caves of Qud.