Zero Escape series, specially 999, VLR is a bit rough in the difficulty and ZTD reaches a nice balance but the plot is oof. The hitman games are far as I am concerned puzzle games but that is a bit of a hot take for people. A different out there choice that scratches the itch I think is Prince of Persia Sands of Time. Warrior Within and 2 Thrones has better combat but combat matters there way more and it is emphasized. Think of it like playing Uncharted and Tomb Raider, not puzzles 24/7 but it has them.