Do you really want just recommendations for science fiction, or do you want recommendations for fantasy too? You mention that you like Stephenie Meyer’s books and that you like American Gods. Both are fantasy (or maybe horror) rather than science fiction. Yeah, you can say that I’m being picky, but I need to know exactly what you want. My twenty favorite science fiction works more than 25,000 words in length are Olaf Stapledon’s First and Last Men and Starmaker, Philip José Farmer’s Riverworld series, Frank Herbert’s Dune, Walter Miller’s A Canticle for Leibowitz, Alfred Bester’s The Stars My Destination, Ursula K. Le Guin’s The Left Hand of Darkness, Philip K. Dick’s The Man in the High Castle, Frederik Pohl and C. M. Kornbluth’s The Space Merchants, Theodore Sturgeon’s More than Human, Roger Zelazny’s Lord of Light, Arthur C. Clarke’s Against the Fall of Night, Ken Grimwood’s Replay, Stanislaw Lem’s Solaris, H. G. Wells’s The Time Machine, Joe Haldeman’s The Forever War, Clifford Simak’s City, Michael Frayn’s The Tin Men, Samuel R. Delany’s The Einstein Intersection, Isaac Asimov’s The End of Eternity, and Robert Heinlein’s Stranger in a Strange Land. I can give you a list of my favorite fantasy if you prefer.
Stephenie Meyer was a joke; I figure most people could figure out who my favorite author was based on my user name. I’m not actually a Stephenie Meyer fan. As for American Gods, that was in response to a suggestion someone else made. I like fantasy, but not nearly as much as I like sci-fi, and I’m aiming strictly for sci-fi recommendations in this thread.
From your list, I’ve read (and enjoyed) The Man in the High Castle and The End of Eternity. I’m getting a number of recommendations on The Forever War, and will probably move that up pretty high on my list.
Lot of votes here for “The Stars, My Destination”. Maybe it’s just me, but I preferred Bester’s “The Demolished Man”.
Another vote for “The Forever War”, and I have read “The First Fifteen Lives of Harry August” and enjoyed it but there are many better books out there. When it comes to SF, I’m a classicist at heart. See if you can find some Leinster.
OK, so there really is only one choice to me:
The Book of the New Sun by Gene Wolfe
Dune isn’t the Lord of the Rings of science fiction. BotNS is.
If you do want a fantasy suggestion for a lover of science fiction, try Master of the Five Magics, by Lyndon Hardy. He’s a PhD physicist, and it shows.
Stranger in a Strange Land is the absolute worst place to start with Heinlein, and I cringe whenever I hear anyone starting with it. Everyone either loves it or hates it. If you love it, then you’ll also enjoy other Heinlein works… but if you hate it, you’ll still probably enjoy other Heinlein works. Read any or all of the juvies, read The Moon is a Harsh Mistress, Double Star, and Starship Troopers, read a few others, and then maybe try Stranger, and if you turn out to hate it, don’t feel bad about it.
I recently read a volume titled “The Science Fiction Hall of Fame”, full of classic short stories. There’s a few stinkers in the bunch, and some authors got short-changed by the policy of only including one from each author, but most of the decisions were very good.
I second the remarks about most of Heinlein’s juveniles, and would add that Glory Road is a great novel.
I also recommend Poul Anderson, my favorite science fiction writer; Stephen Baxter, Kim Stanley Robinson, Leigh Brackett, and Roger Zelazny.
The first novel is on that list, but I would read the entire Cities in Flight quartet by James Blish.
It’s a graphic novel, but I consider Alan Moore and David Gibbon’s The Watchmen to be one of the best SF novels.
The Maker of Universes, the first of the World of Tiers series by Philip Jose Farmer, is the first SF novel I ever read, and I still think it’s first rate. The next three books in the series are all right, but I quit reading the series after The Lavalite World.
The late Harlan Ellison wrote quite a few short stories worth reading.
I second CalMeacham’s remarks about Frederic Brown, Cordwainer Smith, and the Sting in the Tail writers. Tenn and Sheckley are hilarious.
Fritz Leiber wrote wonderful fantasy and science fiction. For SF, I recommend The Silver Eggheads, another hilarious novel, and for fantasy I recommend Conjure Wife and the series about Fafhrd the Barbarian and the Grey Mouser, at least the first five books.
He’s usually considered a horror writer, but many of H.P. Lovecraft’s later stories are science fiction. I especially recommend “The Shadow out of Time.”
I second Jack Vance, one of the best writers, IMO. To Live Forever and The Blue World are excellent novels.
When it comes to Herbert, I think Dune is the best SF novel ever written. However, Dune Messiah blows chunks the size of a whale. Children of Dune and God-Emperor of Dune are worth reading, I think, but they are turgid at times. You might consider reading his books Under Pressure, Whipping Star, and The Santaroga Barrier.
Add another vote for David Brin. He’s probably the biggest post-Golden Age writer in science fiction. His Uplift series is great but I don’t know if I’d recommend starting out with a multi-volume series like that. Instead I recommend either The Practice Effect (if you enjoy the lighter end of SF) or Kiln People.
Peter Hamilton: Like Brin, he’s written some huge series. So I’d recommend starting with a single novel like Fallen Dragon or Great North Road.
Robert Charles Wilson: I’d recommend The Harvest or Last Year as good places to start with him.
Robert Silverberg is, in my opinion, the greatest living SF author and arguably the greatest of all time. He’s also incredibly prolific; he’s literally written hundreds of books. Some I would recommend to check him out are The Book of Skulls, Dying Inside, Hawksbill Station, Lord Valentine’s Castle, Nightwings, and Up the Line.
John C. Wright’s Golden Age trilogy ought to appeal to an Asimov fan; it’s hard sci-fi with a very methodical writing style and a hint of puzzle-solving. It’s also some extremely creative world-building.
John Barnes has written several short fun novels. Start with The Sky So Big and Black for hard sci-fi or Kaleidoscope Century for an elaborate puzzle structure.
I will second the recommendation for Robert Charles Wilson but suggest starting with The Chronoliths. It’s a novel of time travel and world politics that fits together perfectly on its own terms.
Vernor Vinge’s Peace War novels have an Asimov-like style. However, his space-opera classic, A Fire On The Deep, is way overrated in my opinion.
The only Niven I have enjoyed are his collaborations with Pournelle; they seem to have complemented one another.
The Forever War is a bit of a period piece, in my view.
Metrophage by Richard kadrey a must read …when my english teacher gave it to me she said “it’s a great book but the politics are way out there”
Almost 30 years later the perdictions he made are awlfully damn close to coming true…
For Poul Anderson, I like Fire Time.
You might enjoy Three Hearts and Three Lions. The lead character is an engineer, and he spends much of the book trying to explain fantasy tropes with hard-sci-fi terminology. 
Although it’s a connected series, Sundiver,* Startide Rising* and The Uplift War all work well as standalone books. It’s just the Jijo/“Uplift Storm” trilogy that doesn’t.
Do you have a link? I haven’t read an anthology in a long time, but it’s a great way to “collect” a lot of small gems. If the anthology is good.
I’m guessing this is the anthology in question: The Science Fiction Hall of Fame: The Greatest Science Fiction Stories of All Time.
It really is a good anthology, and one that several of us have recommended here on the SDMB before. I might even go so far as to recommend it as my “If you only read one science fiction book…” selection. The downside is that it’s fairly old: it was originally published in, I think, 1970, and all of its stories are from well before then, so it doesn’t show you what’s been going on in science fiction since then.
A Canticle for Leibowitz - Three dystopian stories in one!
The first part is a post-apocalyptic (6 centuries post) anti-intellectual dark ages and an abbey that still copies small amounts of knowledge, and shopping lists, preserved from before the nuclear war. The middle sees that society a couple centuries later about to break out of those dark ages. It’s marred by competition and war between the city-states that have emerged. The final sees an even more technologically advanced society with two major world coalitions building towards yet another nuclear war.
Repeat as necessary.
If you simply want a fairly complete view of science fiction short stories over the past thirty-five years, read all of Gardner Dozois’s best of the year anthologies, including the one that just came out. Yeah, that’s a lot of work, but you can learn all about short science fiction from 1983 to 2017. Also, note that there are three volumes in the series The Science Fiction Hall of Fame, one volume for short stories and two for novellas. Those cover 1929 to 1964.
If you can find it somewhere, Adventures in Time and Space is the definitive collection of Golden Age stories, and shows where a lot of things originated. Good reading also, if not exactly modern. The wiki entry says it is out of print again, though. Much better than the Treasury of Science Fiction, also mentioned. Read it with the Science Fiction Hall of Fame, not instead of. That is good also.
No love for Ray Bradbury here?
I loved The Illustrated Man and The Martian Chronicles, for starters.
(I didn’t read the whole thread, but did a search for “Brad” and didn’t get any hits).
My personal opinion is that you’re better off introducing somebody to an author in a work that is self-contained. Any book in a series, even if it’s a stand-alone story, will refer to events that happened in other books.
This is especially a factor with Brin who has left several large gaps in the Uplift setting that he’s never written about.
Not sure I’d agree. I mean, for example, I wouldn’t introduce people to Banks through Feersum Endjinn or even Against A Dark Background. Sometimes, an author’s most fully realized universe is the best hook.
If I was introducing someone to Peter F Hamilton, I’d give them Pandora’s Star, the first in a series.