"Mystery" is kind of a large umbrella term that covers so many sub-genres on its own that when people say "yeah, I like mystery," they could mean a wide number of things. There's the classic Golden Age, "murder in a manor" type of deal, that puts the plot and the tricks/puzzles front and center but has characters made out of cardboard. There are the pulps, with well-known tropes, but good atmosphere, well-structured, convoluted plots that take advantage of aforementioned tropes, with twist designed to get you to at least feel something for the characters. Then there's your more modern thrillers/psychological mysteries, that feature ominous serial killers, mysterious bombers, government plots; and put out most of their clues in the background, in the midst of more exciting scenes. Of course, there's also the more metaphysical kind of mystery -- like, say, a Murakami book.
I've generally been a fan of that first type, the Golden Age kinds of stories, for years now. My favorite sub-type are the impossible crimes (John Dickson Carr and alike). But I've admittedly grown pretty tired of them, precisely because I found the characters pretty uninteresting in the long run. I feel like part of why it died out was because their audience at the time started to have the same experience.
(Hell, most of my writing output for the past couple of years have been the Golden Age-styled locked room murders, but even then I've consistently made the plots and characters surrounding those murders weird, modern and near-psychedelic, knowing I'd get way too bored trying to keep it like the classics. And even then, I've kind of gotten tired of doing those, too!)
But overall, I say almost all stories you've seen praised as "page-turners" feature some level of mystery. Maybe not in a "who killed Mr. Rogers" kind of mystery, but a general tease that keeps the reader guessing and intrigued. We all fundamentally want an answer to a question when it's presented to us. It's how we react when presented those questions, and how long we're willing to wait for the answers, that determines what kind of mysteries best suit us.
