Ultimately, adventure games boil down to pixel hunting and trial-and-error, neither of which is particularly fun.

The trial-and-error can be fun, though, if the developer plans for it. Certain games make humorous things happen when you goof up.
The biggest argument against "linear isn't entertaining" is movies. There are certain movies you can watch over and over again because they're compelling.
Similarly, there are certain games you can play over and over again because they're compelling.
Yes, many of them, if you "take the story out" there's not much left, but that's because the story is what's important. There are also those where the story is awesome, and the gameplay is interesting.
I'm sure there are others for whose Sam and Max isn't fun anymore, and that's their prerogative. It was still fun (and funny) for me a year ago when I played through it again.