John Sandford’s Prey series (Shadow Prey, Hidden Prey, Mortal Prey, etc.) is excellent, IMHO.
(Click on the books for a synopsis.)
Robert Crais’ novels are all good, IMHO. That mostly means the Elvis Cole/Joe Pike books, but his others are good too. Elvis is heavy on the smartassery, so (having not read Hiassen) I don’t know if this gets you into cutesy territory or not, but the plots can be pretty intense.
I also like Lawrence Block’s “The Burglar Who…” series. This might be too cutesy for you, but try one and see.
Wow. I would second those choices. Odd combo; never thought I’d run into someone who likes the Kinkster!
Kinky and Vachss are very similar–the adventures of a group of misfits in NYC. While Kinky is funny, Vachss is more roman noir
The Brother Cadfael books by Ellis Peters are absolutely wonderful, even being set in a monastery in the 13th(?) century. The characters for the most part aren’t characters – they’re people. The Brother Cadfael mysteries aren’t just good mysteries – they’re good books.
The same goes for the Catherine Levendeur mysteries by Sharan Newman. They might be a little “girly” for you, but the books nail the atmosphere of 12th-century France (she says as if she’s been there). The first book is “Cursed in the Blood.”
I’ve read a couple of his collections of short stories, and your description is spot-on. 
If you don’t mind your mysteries to be more thriller-like and your hero to be more on the supply-side of crime, Barry Eisler’s John Rain series is awesome. Rain is a half-Japanese/half-American assassin. Though the setting is Japan for the most part.
That sounds good to me! Thanks for the suggestion.
Elmore Leonard is an oldie-but-goodie. He’s over eighty and still going strong.
Are you familiar with K.C. Constantine? His Mario Balzic novels are more accurately Police Procedurals than mysteries, but excellent IMO. Wiki page.
When you look for Westlake novels, don’t forget to include the Parker series written under the Richard Stark pseudonym
In the past, I’ve enjoyed Ellery Queen, but it’s been years since I’ve read them, and I suspect that they don’t translate well into the 21st Century.
Someone recommended Henry Wade, a British writer from the 30’s and 40’s. I’ve only read one – New Graves at Great Norne. I liked it a lot. Wade is good with atmosphere and with observation. Every character was richly drawn, even the walk-ons.
I’m very fond of the Civil War mystery series written by Owen Parry. The hero is a short man (and he’s sensitive about it). He’s a bit judgmental and prejudiced about Irish and Catholics and drinkers and women and the upper classes, but he has a good heart and he’s learning.
I think the Russian writer Boris Akunin is very good. It takes awhile for his books to get translated though. I’ve read just three. They’re all different – no rehashing of plots – intelligent and witty.
I also like William Lashner but watch out, because at least one of his early books has been published under two titles. (I hate buying the same book twice.) Try Veritas and Hostile Witness.
Dan Simmon’s Joe Kurtz books are fast and funny – they’ll make you wonder why they haven’t been filmed.
Michael Connelly, John Connolly, Rennie Airth, Greg Iles, Doug Preston & Lincoln Child have all written mysteries/detective novels that I’ve enjoyed.
Joe Lansdale’s Hap and Leonard books are good too, but they’re more like buddy-adventure stories than mysteries.
j d robb is good. warning: there is wild and crazy sex.
carol o’connell is fantastic. mallory is just unreal.
Thanks for all the suggestions. I’ve read one or more books by close to half of the authors mentioned (and a majority of their output in the case of Robert Crais, Stout’s Nero Wolfe series and Ross MacDonald’s Lew Archer book*).
I need to pick out a few at the library and go from there.
*I know he wrote quite a few Archer mysteries but the plots tend to be remarkably similar, with stock characters including the wayward but misunderstood youth, the seemingly respectable man whose past conceals a dark secret, the emotionally confused young flower of womanhood to whom Archer is attracted and the older but still nubile woman with whom he has a brief fling. 
JD Robb is a pseudonym for romance novelist Nora Roberts, just so ya know.
If you don’t mind some of the older stuff, you might want to try Rex Stout’s Nero Wolfe stories.
Sorry, I will try to answer tomorrow, but wanted to get a post in so that I am subscribed.
Seconded.
I like Janwillem van de Wetering’s Amsterdam series about two police detectives. I don’t think this counts as an exotic location, because the author is, you know, actually Dutch so Amsterdam is a perfectly normal place to solve crimes. They’re solidly in the “cops solving mysteries” genre. He writes in Dutch and then does his own translations, they’re not difficult to find in English.
Tony Hillerman’s Joe Leaphorn mysteries are excellent, even if you have never been to the Southwest. And you can always read his The Fly on the Wall, which is his only non-Navajo one. The hero is a reporter in an unnamed Mid-America state capital (although Hillerman subsequently said it was Oklahoma City; how’s THAT for non-exotic?).
Elmore Leonard is fantastic. I’ve recently started getting into him.
The old guys like Dashiell Hammett and Raymond Chandler still hold me spellbound.