**Chronos **said it perfectly: “The Moon is a Harsh Mistress is quite possibly the best science fiction novel ever written by anyone.”
After that a list that includes Rolling Stones, Glory Road, Door into Summer, Starship Troopers, The Puppet Masters and oddly* Waldo & Magic Inc.*
The other one to avoid, indeed that we should all agree to pretend does not exist, is Farnham’s Freehold.
Also Sixth Column, which cannot be laid entirely at RAH’s feet, since he wrote it from an outline by Campbell. When the guy who buys your stories gives you an outline, you by Og write the story, no matter how racist the outline is.
I’d start with the shorts. You get a good feeling for his writing, they’re his earlier (and often better) stuff, and short fiction has (in my opinion) a tendency to be better than novels anyway. A combination of The Past Through Tomorrow and Off the Main Sequence will get you almost all the short fiction Heinlein wrote, with The Past Through Tomorrow being the Future History and Off the Main Sequence being a more general collection. The Fantasies of Robert A. Heinlein should complete the set, with some overlap of Off the Main Sequence.
I believe the first Heinlein I read was Starship Jones. My parents had a copy lying around, so that’s what I read. There may be better places to start, but it’s a good one.
I’d recommend Double Star as a first read. It’s one of Heinlein’s early books, it holds up well (I’ve reread it this year) and the plot is accessible to people unfamiliar with Heinlein.
Next I’d recommend one of his better juveniles: Podkayne of Mars, Citizen of the Galaxy, or Farmer in the Sky are good.
The Moon Is a Harsh Mistress is generally considered the best of Heinlein’s later work. He does occasionally veer into political preaching but it’s a novel about politics so it fits here.
The Puppet Masters is a good thriller although there is some cold war stuff that’s dated now.
Some I wouldn’t recommend as a first read: Glory Road, it’s not typical of Heinlein’s work and quite frankly the pacing is weak; Starship Troopers, there is a good story here but I think its fans forget how much politics are mixed in; The Door Into Summer, another good story but there’s a creepy sexual vibe that will throw a lot of readers off.
His juveniles are his best IMHO. Have Space Suit, Will Travel; Between Planet; Time for the Stars and Tunnel in the Sky are my favorites.
Not a bit. The politics are some of the best parts. I always wanted to be Col. Dubois as a teacher. 
OK, I think *The Moon is a Harsh Mistress *and Starship Troopers are arguably his best adult works. But although two other people have mentioned it, nobody has discussed Double Star.
Along with the other two I really love that book. The protagonist is an actor offered a job doubling for a ranking political figure. His political team can’t reveal he’s been kidnapped by his opposition, for the best of reasons. Larry has a tremendous ego, but he also has a sincere worker’s ethic, and what comes of that is quite unusual.
Read the other two, but don’t forget to read Double Star.
And Starman Jones has an unusual ending, as such stories go. Don’t forget it either.
The guy doesn’t end up with the girl!
I always wanted to HAVE Col. Dubois as a teacher!
Yet I learned a lot from those juveniles. The first Jewish character I ever remember reading about was in Rocket Ship Galileo, one of the boys who built the ship.
Stupid me. Starman Jones. I even typed it properly to look it up on Wikipedia, and I still couldn’t get it right when I posted.
One other collection that may be worth looking into is Expanded Universe. While a lot of it wouldn’t be a good place to start, his writings about the trip he and his wife took in the USSR back in the 60s were still amusing and fascinating reading, even to a guy like me born in the early 80s.
A lot of people don’t seem to like Beyond This Horizon. When I read For Us, The Living after it was published I realized that I had seen an awful lot of it before in a better form in Beyond This Horizon. It’s not a bad book, but it’s another one I probably wouldn’t start with.
I would disagree with the creepiness, but it probably is safe to say that he was exploring how close he could get to the boundary of creepy without crossing it. But yeah, good point that it might not be the best first book to read.
And Baker, I’ll agree that Double Star was very good. The fact that it’s not being mentioned more really says more about the quality of the other works that people are mentioning.
My favorite of the novellas is If This Goes On… also published as Revolt in 12100
Fore my money The Moon is a Harsh Mistress was about his best.
I also love The Puppet Masters, one of the first of his that I read. Please note that older versions were cut to fit the mores of the time. Some 15 years ago the text was restored, and it makes a difference. If you can, get a recent copy of the book. It reads like James Bond Meets Invasion of the Body Snatchers, but please note that the book predates both James Bond and the book Invasion of the Body Snatchers (and, of course, all film versions). In fact, when Heinlein submitted the manuscript he apologized for re-treading such a hoary old theme (Finney was a Johnny-Come-Lately to the idea, despite the prevalence of his work in cinema), but his treatment is one of the very best, and blows Finney out of the water. Heinlein’s own book has been filmed twice (once unauthorized, as The Brain Eaters), but neither version really does the book justice.
Stranger in a Strange Land is, of course, one of his most recognizede bookis. It’s not really typical Heinlein, but it is definitely a great read. Please note that this one, too, was cut before its initial publication, and that circa 1990 the original text was finally in print. Get a later version if you can. The audiobook version is unabridged restored text.
I like all of the juveniles, which are better than most books intended for adults. I’ve even come to like the first of them, Rocket Ship Galileo, after listening umpteen times to Spider Robinson’s audiobook version of it. But it’s far from the best of the series. Space Cadet, his second, is much better.
I agree about Double Star, a short book but one of my favorites.
I don’t recommend The Number of the Beast (the first book of his I read “new”, and a major disappointment), For Us, the Living (Heinlein’s long-lost first novel, and it shows. He didn’t want it published. For fans and completists, it’s fascinating, but it ain’t up to his standards), and Variable Star seems to me much more Spider Robinson that Heinlein, despite Robinson’s working from Heinlein’s outline.
It’s not science fiction, but I loved Tramp Royale, Heinlein’s account of his round-the-world trip. And his Take Back Your Government is a fascinating piece of fossilized political how-to-do-it.
Robert Heinlein is not one of my favorite authors, but I’ve read some of his work. And the one I remember most fondly, liked well enough to re-read several times is Friday. One of his later works, more adventure than sci-fi, although it’s in a futuristic setting. Kind of surprised no one’s mentioned it here, or maybe it’s just my offbeat taste in literature 
You know, I loved both of those books. They definitely weren’t classic Heinlein (I’ve read most of Heinlein’s books over the years), but I loved For Us, The Living as a fascinating look into a very alternative political system, and even though Spider definitely left his mark on Variable Star, it was still a very enjoyable story.
I wouldn’t recommend either as your introduction to Heinlein, though. I’d recommend Friday - I don’t adore his juveniles for adult readers, and I think Friday is a good, accessible romp. Or The Cat Who Walks Through Walls - another good romp.
Oh, God no. Cat is not where to start with RAH. It only makes any kind of sense if you’ve read all that came before. And not a lot of sense then.
Probably easier to make a list of works to be avoided the first time around…
Space Cadet
I Will Fear No Evil
Farnhamn’s Freehold
The Number of the Beast
Job is pretty damn good, everyone forgets that one.
I was thinking of starting a thread like this myself. Last year, I decided to see if I liked Heinlein (he, Clarke and Asimov are touted as the Big Three of science-fiction, and I love the other two) and bought a pile of his books at a second-hand book sale. I started a few of them, but ended up tossing them aside when the sexism or Christianity bashing got to be too much for me. But maybe I just chose the wrong ones. The books I have are Stranger in a Strange Land, I Will Fear No Evil, Time Enough For Love, The Number of the Beast and Job: A Comedy of Justice. The ones I started and gave up on are I Will Fear No Evil and Job: A Comedy of Justice. Can the fans in this thread tell me if any of the books I have are worth trying?
(emphasis added)
I think there’s a bit of background that’s helpful, or at least interesting, to know about the overall story line. (Slight spoiler here, no biggie):
I believe the story parallels the history of Australia. A far-away penal colony from which there can be no return, then a revolution for independence. (Can some oz-lander comment if I know what I’m talking about here?)
Well, it’s clear that you don’t like his late work, which all of those are (except for Stranger, though it’s similar to a lot of his late work). You clearly either picked up the remains of a pile that other people had left, or else someone who donated the books was a big fan of his later work. Some people love that period, other people hate it. If you want to continue, pick books with copyrights before 1970; they’ve got much, much less sex and politics.
Actually, I thought it
came closer to paralleling the independence movement in Ireland. A distant occupying force that uses the occupied to produce cheap food and goods? Actively seeking to bait the oppressive occupiers into atrocities in order to drum up local support? Admittedly, I don’t know much about Aussie history, though.