…probably doesn’t matter which Hillerman book you read…
How about the Spenser books by Rober B. Parker? Especially the early ones. Talking about Parkers… there’s always Donald E. Westlake (aka Richard Stark) to consider (for the other side of the law).
I’d start with Listening Woman and then go on to all the rest of 'em. 
For a more Gothic, literary, but contemporary mystery, try The Thirteenth Tale, by Diane Setterfield. It’s smart, creepy and utterly absorbing.
If you like a lot of smartasesry mixed in, you might like Carl Hiaasen’s books. IMO, his best is Skinny Dip.
Preston and Child’s books have a supernatural element and a great detective character, FBI Agent Aloysius Pendergast. I skipped the first book, Relic because I thought the writing was clunky, but it gets much better in the second, Reliquary, and the third is one of the best in the series. Here’s a list of the books in order. They’re quick reads and very entertaining:
Relic
Reliquary
The Cabinet of Curiosities
Still Life with Crows
Brimstone
Dance of Death
The Book of the Dead
The Wheel of Darkness
Cemetery Dance
Fever Dream
…and you should probably stop somewhere after the Book of the Dead… or is it The Wheel… Anyways, before the Tulpa thing… the series goes downhill from then on… the protagonist suddenly becomes a lobotomized Sherlock Holmes.
But that’s just my opinion.
If you like Sherlock Holmes, another good suggestion (on the top of my head because I just picked up a copy at a yard sale today) is The Name of the Rose, by Umberto Eco. It’s a murder mystery set in a medieval monastery, with a very Holmesian detective.
Nevada Barr, Blind Descent. Set in a cave. Very scary setting. Lots of suspense.
If you like lighter fare, there is the entire “#1 Ladies Detective Agency” series on Kindle. My wife loves them.
I’ve read Name of the Rose… I found it hard to slog through. I’m probably going to enjoy modern settings more than “classics” at this point in time (just based on what my mood has been).
Thanks for all of your recommendations, I’ll look and see if any of them are available for Kindle (for the foreseeable future I’m not buying hard copies of books, since our current house is too small to have book cases up, and I don’t do library books*.)
*I read in the bathroom and assume everyone else does too… I can’t help but think about hundreds of people holding a book while taking a dump when I read a library book. The ick factor just gets to me too much.
There’s a writer by the name of Jane Stanton Hitchcock who writes delightful present-day society/crime stories. Most aren’t whodunits, but the most recent one is and the ending is quite a surprise. The title is Mortal Friends.
As you’ll see from the link, her other books so far are:
Social Crimes
One Dangerous Lady
Trick of the Eye
The Witches’ Hammer
Amazon can probably tell you enough about them for you to decide if they’re something you’d be interested in. I’ve read all but the last one (which I’ll get to soon) and I’ve enjoyed them all quite a lot. I wish she were more prolific.
If you think you’d enjoy some crime fiction with a handsome, charismatic and badass-when-he-has-to-be detective, good development of secondary plot lines and characters, and really bad bad guys who usually get what’s coming to them, I’d recommend the Prey series by John Sandford. Here’s a link showing them in the order in which they were written. You can click on the titles for a synopsis. I’d start with the first one and work my through in order, though, since some of the characters and events carry forward into subsequent novels.
Jonathan Carroll’s The Land of Laughs
Agatha Christie’s Ten Little Indians is a great one or two day read.
Otherwise known as …and then there were none.
I haven’t read the Judge Dee Mysteries, but otherwise, I like them all. I don’t care for Rex Stout’s non-Nero stories, by the way. The Nero Wolfe stories are fantastic, and I agree that Goldsborough did a great job in resurrecting Nero.
Another good source, besides us, is The Sleuth of Baker Street - one of my favourite bookstores in Toronto. The Newsletter comes out every couple of months, (it’s available online from that above link…) and is a fantastic resource for what’s new in the mystery genre.
I’m a big fan of some of the ‘current’ UK writers.
Reginald Hill - start, if possible, with the third Dalziel and Pascoe book and then work your way forwards and backwards. ‘A Clubbable Woman’ and ‘An Advancement of Learning’ are good, but it’s from ‘Ruling Passion’ onwards that you get what the fuss is all about.
John Harvey (not to be confused with 'Jack Harvey, which is a pseudonym of Ian Rankin’s…)
Robert Goddard (not the father of rocket science.)
and Barbara Nadel
I will suggest:
Dick Francis. Thrillers with some sort of horse racing tie-in. Energetic and heroic main characters. Doesn’t really matter which one, but I’ll recommend the first of the Sid Halley books: Odds Against.
Lauren Henderson. Funny artist sleuth with a bad attitude. The third book in the Sam Jones series is the first I can ever find in the US: Black Rubber Dress.
Some people who like Janet Evanovich like Sarah Strohmeyer. Bubbles Yablonsky is a dippy-smart hairdresser: Bubbles Unbound
Kate White’s Bailey Weggins series. Bailey is a reporter who stumbles across all sorts of stories: If Looks Could Kill
Laura Lippman’s Tess Monaghan series. Tess is a PI in Baltimore: Baltimore Blues
The Alienist by Caleb Carr. Set in Turn of the century New York, it follows a psychologist and his team as they race to solve the murders of child prostitutes. I love that they have to do this without the benifit of modern forensics. They utilizes controversial and brand new techniques such as finger prints and profiling.
Here’s my thread on this topic last year. I’ve still not even scratched the surface of the recommended authors but I’m having a great time working my way through the list.
Opal:
Yes, both names are authors. Barr sets her mysteries in national parks, investigated by a park ranger, Anna Pigeon. Hillerman, now deceased, set his novels in the Navajo nation with investigations by Navajo police officers, Joe Leaphorn and Jim Chee.
Barr’s first book, “Track of the Cat,” wasn’t great but it set up the characters. Hillerman’s first, “The Blessing Way,” also set up the characters, but was a very good read which continued throughout his series.
I also like Lindsey Davis. Her detective, Marcus Falco, is an informer in Rome during the reign of Vespasian.
Also good are Caleb Carr’s “The Alienist,” and “The Angel of Darkness,” both good historical mysteries.
And I have to give kudos to Mark Frost’s “This List of Seven,” and “The 6 Messiahs,” not really mysteries in the traditional sense, but good page-turners.
Also, “Devil in the White City” is really good, but it’s not a novel nor a mystery, but it reads as if both. By Erik Larson.
Totally loved Van Guliks work, you don’t hear his name often nowadays, I also enjoyed Rex Stout a lot, but when I tried Mortimer I just couldn’t get into his style.
It was far too oily for me and I gave up on him.
The Grand Old Master of the modern day detective novel was Ed McBain.
Kinky Friedman is very funny and Ansrerw Vachss very roman noir.
I love culinary mysteries, where getting recipes are like prizes in a box of Cracker Jack. My favorites was Diane Mott Davidson and Joanne Fluke.
Try the Joe Pitt seriesby Charlie Huston. Start with Already Dead. There are only five books in the total series.