Portal (1 and 2) and The Talos Principle are the only puzzle games I've played that not only had a story, but also managed to make the puzzle gameplay actually make sense within the story. Like, there is an in-universe explanation for why you are solving puzzles. I'm sure there are other games that do it, but those are the only ones I've played and they were fantastic. That's a hard thing to pull off -- how do you make a compelling narrative, complete with characters, around "moving some boxes?"
Looking forward to playing the sequel. Also, the original is $3 on Steam right now!