I enjoyed the puzzle book Leviathan by Jason Shiga. It's a sort of choose-your-own-adventure comic book. (Shiga's made other such CYOA comics before, you might remember Meanwhile… from some years back. Yeah, that was him.)
In the story, you are a brave adventurer on an archipelago of truth-tellers. It's kinda like being on the island of liars and truth-tellers from the logic riddles, except with a better backstory. Everybody's afraid that if they lie the sea monster Leviathan will smite them. Your quest: find a wand to control Leviathan. Along the way, you talk with a librarian, sailors, and suchlike.
I didn't actually get the physical book yet; it's sitting in my hold-stack at the comic book store. Too impatient to wait for my next store visit, I played the computer game version. It ran fine on my Linux box with the years-out-of-date 3D card (which shouldn't be surprising for a 2D game, but it nevertheless pretty darned pleasantly surprising these days)..