Personally I only enjoyed maybe 3 puzzles in the game: Shelly´s Gym, the Heracross/Pinsir puzzle and the one in the Blacstream Factory. Shelly´s puzzle feels most Pokemon-esqe to me and I like the concept of the Heracross/Pinsir puzzle and the Blackstream Factory puzzle. Most puzzles are tedious and not really fun for me. I didn´t even like the puzzle in the Valley for the sole reason I had to teach someone Rock Smash again. Yeah, it´s a TM and you can forget them but still more or less a useless move. I really wish Gamefreak never invented the concept of HM and instead gave us Items.
Edit:
Also a PC before the Steelix battle without fainting beforehand would be really cool