Throwing out new names at random as they come into mind:
30s
John Dickson Carr
Anthony Berkeley
Stuart Palmer
Erle Stanley Gardner
40s
Craig Rice
Phoebe Atwood Taylor/Alice Tilton
Edmund Crispin
Jonathan Latimer
Clayton Rawson
Cornell Woolrich
50s
Mickey Spillane (if you’re never read him you have to read one to see what the fuss was about)
Oh yeah. Awesome locked room mysteries with Dr. Gideon Fell!
And even more awesome locked room/impossible crime mysteries with Sir Henry Merrivale.
And the best (IMHO) Sherlock Holmes pastiches ever, both with and without Adrian Conan Doyle.
You should at least try the Merrily Watkins series. It’s contemporary, but reads old.
Rex Stout - his Nero Wolfe series is really good.
Too Many Cooks, League of Frightened Men, Some Buried Caesar are three of my favorites.
Phoebe Atwood Taylor
Charlotte MacLeod
Quirky, regional characters.
I’ll suggest E.C. Bentley’s Trent’s Last Case
I’ll also third Ellery Queen. I especially recommend The Greek Coffin Mystery, The Egyptian Cross Mystery, and *Four of Hearts *from the 1930’s; Calamity Town, The Murderer is a Fox, Ten Days’ Wonder, and *Cat of Many Tails *from the 1940’s; and The Origin of Evil, The Scarlet Letters and *The King is Dead *from the 1950’s.
I also recommend James M. Cain. Kate Wilhelm is a contemporary, but I think her Barbara Holloway novels are hard to beat. Marcia Muller writes a pretty good series about San Francisco private eye Sharyn McCone (the earliest are in the 1970s), but I think her best books may be those set in a fictional rural northern California county. Two of these are Point Deception and Cyanide Wells.
John Dickson Carr has been mentioned and I heartily concur. He also wrote under the name Carter Dickson. Whatever you do don’t miss his The Hollow Man, 1935. It was selected in 1981 as the best locked-room mystery of all time by a panel of 17 mystery authors and reviewers. (Wikipedia)
Again, Fredric Brown, also previously mentioned and a master of both SF and mystery. (He’s also adept at the ‘short short’,
I always loved the Ellery Queen novels,authored by Dannay and Lee under the pen-name of Ellery Queen. Very well-constructed whodunnits, from The Roman Hat Mystery, 1929, through A Fine and Private Place, 1971, the year Lee died and Dannay stopped writing. Later novels are ghost-written, most of them not to a high standard.
Nitpick from an Ellery Queen fanatic.
Three* titles are ghostwritten:
[ul] The Player on The Other Side—1963 (ghost-written with Theodore Sturgeon)[/ul]
[ul] …and on the Eighth Day…—1964 (ghost-written with Avram Davidson) (Grand Prix de Littérature Policière winner)[/ul]
[ul] The Fourth Side of The Triangle—1965 (ghost-written with Avram Davidson)[/ul]
All are very good to excellent and better than any of the later books, after Manny Lee got over his writer’s block.
Since Mickey Spillane was mentioned …
I took an interest in mysteries after watching the “Mickey Spillane’s Mike Hammer” TV show in the 1980s (starring Stacy Keach as Mike Hammer). So I hit up my local public library and discovered some good stuff:
Lawrence Block has already been mentioned. Anybody who has read his “Burglar” books knows of Bernie Rhodenbarr’s hobby of learning about patron saints, and that his best friend was a lesbian. My favorite exchange between the two characters (paraphrased from memory - I read this almost 30 years ago):
Carolyn Kaiser: So, is there a patron saint of lesbians?
Bernie: The little Dutch boy.
Carolyn: The little Dutch boy?
Bernie: You know, the one who stuck his finger in the hole in the …
Carolyn: Nobody likes a smartass, Bernie.
H.R.F. Keating really hooked me with his Inspector Ghote series, about a detective with the Bombay (India) police force. I just looked at his Wikipedia page, and was surprised to discover that he just died three years ago. I’d thought he was already dead when I was reading his books in the '80s (hey, we didn’t have the Internet then!) While I was reading his books, I had the good fortune to meet a Christian missionary to India who was able to tell me how to properly pronounce the name “Ghote”.
Georges Simenon: I ate up his “Maigret” novels. And there are a crap-ton of them.
Knock 3-1-2 was made into a French film called “The Red Ibis”. It was also made into an episode of the US TV series “Thriller”.
Harry Kemelman wrote the Rabbi series. This thread reminded me that I never finished reading the later books. I read maybe the first 5 or 6 books. Can’t recall. I need to find copies and correct that mistake. 
I recommend Reginald Hill, the Dalziel & Pasco series, which began in 1970.
Two I’d recommend are Kinky Friedman (very funny) and Andrew Vachss (very dark).
Was it Connie Willis? It was Connie Willis, wasn’t it?
Speaking of, if you like science fiction with a light tone, time travel, and a kind of cosmic whodunnit, you can’t go wrong with To Say Nothing of the Dog.
The Judas Window, by the same author, is another terrific locked room mystery. It features the window in every room that only a murderer can see.
Carr gets tricky bibliographically, so a quick note.
The Hollow Man is titled The Three Coffins in the U.S. It has Dr. Gideon Fell as the detective, so it came out under the Carr name.
The Judas Window came out in U.S. paperback at least once as The Crossbow Murder. That’s one of the Sir Henry Merrivale books, so it was originally published as by Dickson but in recent years they’ve put Carr’s name on it. This is not the same book as The Bowstring Murders, which originally was by Carr Dickson before he changed that to the less obvious Carter Dickson. Both titles have some editions with crossbows on the cover.
Old mysteries which have appeared in literally dozens of editions over the decades can drive you bonkers.
A big +1 on these.
I’d recommend the Harry Stoner series written by Jonathan Valin. There are others better, but it’s a great A-/B+ series. may be hard to find, but a large library might have them.