You could read novels, but I personally think you're going to get a better intro to SF and more enjoyment, and a better chance of finding "your thing" if you read short stories. You can then read the novels you know you'll enjoy. I love SF anthologies, not only because you get a collection of pre-selected awesome pieces, but also you get to sample a ton of different authors with different styles in the same number of pages as reading a novel would get you just a single story and a single author. Also, many consider the short story the ultimate and best form for science fiction.

I suggest anthologies that collect stories over multiple years instead of just "best of the year" collection. For obvious reasons, you get better stories. Here are the best I know of:

• The Locus Awards: Thirty Years of the Best in Science Fiction and Fantasy
  
• The Hard SF Renaissance (One or two stories from this will answer the question of whether you like Hard SF.)
  
• The Science Fiction Century
  
• Twenty-First Century Science Fiction (sort of a sequel to the previous one)
  
• Science Fiction Hall of Fame Volume 1, 2a, and 2b (This is kind of a survey of historical SF, ranging from the '20s to the '60s.)
  
  So you could go historically starting with old stories and working your way more contemporary, in which case you'd start with SF Hall of Fame. But it might be a better idea to start with the most contemporary stuff and go backwards. In that case, you'd start with Locus Awards and start in the back of the book.
  
  In terms of specific authors, I would be amiss not to encourage you to read Ted Chiang. He has written only 13 short stories between 1992 and now, but he's won more awards for them than most SF authors do in their lifetime including the prestigious Nebula, Locus and Hugo awards, among others! READ. HIS. STORIES. He has an awesome anthology Stories of Your Life and Others plus you can buy his more recent stories on amazon.
  
  You should also read Greg Egan. And Enders Game if you somehow missed it. There's also the classic Arthur C. Clarke, either his short stories, or a novel like City and the Stars.
  

Check out Quarter Share by Nathan Lowell. Falls under the category of space opera, but it's a lot better than that. Great writing, funny, and no manipulative endings, with their screams of "buy the next book to find out!"

Normally I don't care for fantasy, but I stumbled across Hounded and found it well written, with a lot of creative, funny ideas. It's just good story telling.

OK this list is all different types of authors and stories, maybe you will find something you like:

Reach for Infinity

Peter Watts, Beyond The Rift

James Alan Gardner, Gravity Wells

Greg Egan, Axiomatic

Cory Doctorow, A Place So Foreign

Michael Swanwick, Tales of Old Earth

John Varley, Persistence of Vision

Edward Bryant, Particle Theory. Stories from 70's & 80's, but solid.

The Best of Interzone. Stories from the British SF magazine.

Dozois has the Annual Best. The stories are all over the board for subjects, with alot of well known current authors, and some relatively unknowns. This is kind of a big clunky oversized book - not great if you want a small paperback to carry around, or read in an airport.

Hartwell's annual SF. This is a small paperback size - usually some crossover with stories also in the Dozois collection.

Good luck.

I don't have any particular examples for the 20s-40s, but if you haven't already, take a look at The Cambridge Companion to Science Fiction. It's got a brief history of various time periods of the genre, plus some great texts about subgenres, themes, and issues involving SF. I'm sure it has some solid recommendations for that time period, too.

I would also suggest incorporating some SF comics/graphic novels, too - Moebius (who drew the picture /r/printSF uses as its banner) wrote and illustrated comics, and he heavily influenced a lot of SF visual media, either directly (as concept artist) or indirectly.

Edit: I'd be really interested in seeing the syllabus for this once you're done, if you're willing to share.

^(Note: these are all books I've read and can recommend from experience.)

David Brin's Sundiver is a detective mystery. Likewise his Existence is a mystery about a recently discovered artifact, though its presentation with multiple perspectives lacks the singular detective tone of Sundiver. It's not as much of a mystery/thriller more of a mystery/adventure. It is also one of the overall best science fiction novels I've ever read; the writing is top notch, the characters superbly lifelike, the tone excellent, and the overall reading experience enjoyable and filled with a realistic optimism.

Gregory Benford's Artifact is an investigative mystery about a strange artifact. His Timescape is about a strange phenomenon.

Jack McDevitt's The Engines of God is an investigative mystery about a strange artifact.

Asimov's The End of Eternity is a classic mystery/thriller.

Alastair Reynolds' The Prefect and Chasm City are both standalone detective mysteries. His Revelation Space is similar, but does not have the same classic mystery tone.

Greg Bear's Queen of Angels and Slant are both standalone detective mysteries.

I seem to recall the Second Foundation (Foundation's Fear, Foundation and Chaos, Foundation's Triumph) trilogy by Greg Bear, Gregory Benford, and David Brin having some mystery aspects. I think one of them at least is a detective mystery, but I can't remember which right now.

Dan Simmons' Ilium/Olympos is a sort of detective mystery, but its tone is much more action/adventure despite the protagonist's undertakings to determine what in the world is going on.

Joan D. Vinge's Cat Trilogy (Psion, Catspaw, and Dreamfall) are detective mysteries.

Julian May's Perseus Spur is a detective mystery. It's pretty light-hearted and a lot of fun to read. Something you would pick up at an airport bookstore and not be at all disappointed with. I can't speak for the other two books in the trilogy, haven't read them yet. Just ordered them off Amazon for $4 a piece.

I could go on, but I think that should keep you busy for a while.

 

^(Edited to clarify the tone of some suggestions. Some are more traditional mystery/thriller, while others are more adventure/mystery, more alike to Indiana Jones than a noir detective.)

Best novel: The Bone Clocks by David Mitchell. Hands down the best novel yet from the author of Cloud Atlas and The Thousand Autumns of Jacob de Zoet. It's a story about the ways we change and even become a different person as we age. It's a story about a secret war between psychic immortals. It's the story of the slow loss of our planet at our own hands. It's sad and funny and poignant. It's Mitchell applying all the experiments with prose, narrative, and character perspective from his previous novels to built a coherent linear narrative.

Best novellette / novella (I'm not sure which it is): The Colonel by Peter Watts. I think I liked this even more than the book it was an intro for, and I liked Echopraxia a lot. A near-future posthuman super-soldier/-spy mourns for his lost son.

Speaking of:

Best novel: Echopraxia by Peter Watts. A dumpy scientist, said super-solider, a vampire, and a religious order/hive-mind explore the power array circling our sun for signs of alien infestation. Watts is a master of pairing hard biology and physics with out-there yet plausible philosophy of mind and identity.

The Quantum Thief by Hannu Rajaniemi and The Windup Girl by Paolo Bacigalupi are both amazing, deep, engrossing books with worlds of their own. I cannot recommend them enough.

Also, China Mieville's books are pretty awesome, though more urban fantasy than SciFi. Still worth a read.

Spin by Robert Charles Wilson. It is like Niven and Clarke in that the plot focuses on a big, mysterious object; however, it is a character-driven story first. The hard sci-fi elements, as they gradually emerge, deliver the goods as well. It's a great book; it won the Hugo for a reason.

Edit: Avoid reading the synopsis on amazon. I think it gives away a bit too much.

Have you read the 'Red Mars' series? They're by Kim Stanley Robinson and are pretty much exactly the sort of hard sci-fi + character development that you seem to enjoy. They're also pleasantly topical given Curiosity's successful landing.

If you like that kind of stuff then you must read Richard Paul Russo's Carlucci trilogy, which you can get in one volume. It's excellent gritty, noir cyberpunk at its best.

It came out last month, but I just saw it and scooped it:

The Year's Best Science Fiction: Thirtieth Annual Collection - Dozois

I get really excited when this anthology comes out.

A Canticle For Leibowitz is remarkably deep, more in the spec-fic vein than sci-fi, but an undeniable classic nonetheless.

I've also really enjoyed the "Hall of Fame" short story collections. You really get a sense of the inspirations behind the genre.

Lilith's Brood, by Octavia Butler, previously published as The Xenogenesis Trilogy. Excellent sf!

ETA: The Sparrow and its sequel Children of God, by Mary Doria Russell. I know I keep mentioning this book, but it's that good!

I believe the following meet all the criteria:

• Rendezvous with Rama by Arthur C. Clarke
  
  
• The Quiet War by Paul J. Mcauley
  
  
• Blindsight by Peter Watts
  
  
• Leviathan Wakes - The Expanse by James S.A. Corey (I haven't read this one, but it has great reviews and fits your criteria)

[Hard-Boiled Wonderland and the End of the World] (http://www.amazon.com/Hard-Boiled-Wonderland-End-World-International/dp/0679743464/ref=sr_1_1?ie=UTF8&qid=1372998994&sr=8-1&keywords=hard+boiled+wonderland+and+the+end+of+the+world) is probably his most sci-fi, as well a great starting point.

Try The Quantum Thief a hit-tech, high-energy adventure.

Also,

> .. books aren't sexist or racist but not about those issues ...

Ancillary Justice which folks might not suggest because of its well-known take on gender, but it's not about that at all. It's pace is pretty moderate, though.

The Sparrow. Possibly my favorite book of all time. There is a sequel as well, Children of God.

https://www.amazon.com/Existence-David-Brin/dp/0765342626

For me, it was a different take on "first contact". It's a really fun read, set a little bit further in the future from today.

"Join Us!"

Does it have to be well-told? :P

Grimspace series - Ann Aguire

Friday - Robert A. Heinlein

Stardoc - S.L. Viehl

Blade Dancer - S. L. Viehl

Califia's Daughters - Leigh Richards (post-apocalypse)

Read Bruce Sterling. Sterling is spelled with an "e", not an "i". The "i" is a completely different author. If you've read all William Gibson, then you've already read one book by him, The Difference Engine, co-written by Gibson and Sterling. Specifically - Schismatrix Plus. It is fucking amazing.

The first story is The Microcosmic God by Theodore Sturgeon, and the third is A Martian Odyssey by Stanley Weinbaum.

I haven't read the 2nd one, but the collection is very likely to be The Science Fiction Hall of Fame, Vol 1.

Some top picks for the category I'd call "gripping and fast paced", which I think is what you mean by "plot-driven":

• WJW - Voice of the Whirlwind, also Metropolitan.
  
  
• Gibson - Virtual Light.
  
  
• Warren Hammond - Kop series.
  
  
• You mention Morgan - Thirteen is nearly as good as Altered Carbon. I didn't rate Market Forces, and I haven't tried the new / current fantasy trilogy.
  
  
• Speaking of fantasy, Joe Abercrombie's First Law series.

Schismatrix Plus, that is Schismatrix and all related short stories, is only somewhat opera-ish but it might be interesting nevertheless. It's very short and condensed, establishes a universe with several factions, covers a big period of time.

The three series that come to mind are below:
I enjoyed all 3 for each its own reason. The Solar Clipper one stands out as more unique in my mind. I wish there was more like it.

 
 
 

---

• Starforce by B. V. Larson (Swarm,Extinction,Rebellion,Conquest,Battle Station,Annihilation,Storm Assault,The Dead Sun)
  
  
• Frontiers by Ryk Brown (Aurora: CV-01,The Rings of Haven,The Legend of Corinair,Freedom's Dawn,Head of the Dragon,The Expanse,Celestia: CV-02,Resistance,Liberation,Rise of the Corinari)
  
  
• Solar Clipper Trader Tales by Nathan Lowell (Quarter Share,Half Share,Full Share,Double Share,Captain's Share,Owner's Share)

I enjoyed David Brin's Existence but it's probably not the War of the Worlds style invasion that you're looking for.

Cambridge Companion series and Nortons were always really helpful during my Literature BA/MA years. And they both have ones on science fiction.

http://www.amazon.com/dp/0521016576/ref=wl_it_dp_o_pC_nS_ttl?_encoding=UTF8&colid=2ITSA94IIME2F&coliid=I24VKUCN202HQB

http://www.amazon.com/dp/0393972410/ref=wl_it_dp_o_pC_S_ttl?_encoding=UTF8&colid=2ITSA94IIME2F&coliid=I2YKEOZBVABUJD

I just finished, and rather enjoyed Altered Carbon (Takeshi Kovacs Novels), which also falls into the cyberpunk noir genre. The first one at least, haven't read the rest yet.

It's tightly written, has a unique dynamic tension between the characters and the aliens are truly alien. It's unlike any other science fiction book that I've read.

But don't take my word for it, you can read it here online before the sequel comes out next month.

Just started CS Friedman's This Alien Shore. Female protagonist on the run, from what she doesn't know yet. Set within a far future universe and also entails an exotic computer virus let loose within the systems of the net... as usual very dense in plot and I am getting drawn in so far. Only other novel of her's I have read was In Conquest Born and that was a very good psi-fi/space opera.

I'd suggest finding a short story collection, such as the Gardner Dozois annual years' best, or one of the Hugo winners collections.

I liked the Red Mars trilogy. And the series that starts from Coyote does a good job of making the tech believable, but also telling a timeless story that kids can grok.

Popping back in to check the list of books (some good stuff in here!) and surprised not to see The Windup Girl by Paolo Bacigalupi. He also wrote Pump Six (short stories, some very good), Ship Breaker (aimed at juveniles, but still fun) and The Alchemist (ok, I guess).

I don't know if sci-fi is the best word for it, but I'd be remiss not to mention Hard-Boiled Wonderland.

Let's say "non-famous" rather than "underrated". Most published books don't get rated at all.

• The Quiet War and its sequel were both awesome but received less attention than IMO they should have.
  
  
• Same for Justina Robson's Natural History.

Incidentally, check out this collection of Le Guin's Hainish novels. (Totally worth it by the way.)

Otherwise, here are some suggestions for other authors:

• CJ Cherryh's Downbelow Station and her other Alliance-Union works.
  
• Iain M Banks' Culture series. People often suggest starting with Player of Games which is a solid choice.
  
• Ann Leckie's Ancillary Justice (the first in a trilogy)
  

Eternity Road by Jack McDevitt is an excellent many-years-after-the-apocalypse type story.

Spin by Robert Charles Wilson isn't exactly apocalyptic, but it does deal with end-of-the-world themes and explores how society might react.

Wastelands is an excellent collection of apocalyptic short stories.

This Alien Shore by C. S. Friedman. I'm not sure how many people have read it, but I don't see it mentioned very often, which is a shame because it's a great book.

The Risen Empire and then the sequel Killing of Worlds.

Leviathan Wakes

Try out Heinlein's Book Friday. Depending on the age of your niece, I'd suggest reading it first before recommending it to her.

There's a Carlucci omnibus of all three novels available.

The Cambridge Companion to Science Fiction

Coyote + sequels by Allen Steele.

Red Mars + sequels by Kim Stanley Robinson.

40,000 in Gehenna by CJ Cherryh, now available in Alliance Space.

Spin by Robert Charles Wilson has a somewhat similar idea, except instead of humanity expanding off-planet, the universe itself ages faster.

Hard-Boiled Wonderland and the End of the World by Haruki Murakami.

http://www.amazon.com/Echopraxia-Peter-Watts/dp/076532802X

Nathan Lowell's Solar Clipper series (start with Quarter Share) fits the bill perfectly. The protagonist is practically a Mary Sue, but it's actually quite refreshing to have a character who has no flaws and for whom everything goes right.

The Windup Girl is different kind of apocalyptic tale, won the hugo and nebulla awards. Hard sci fi with a very human touch.

This Alien Shore is one of those single books that actually make me want to read more in that universe.

Stranger in a Strange Land is controversial, thought provoking, and while a couple of characters will show up in later Heinlein books, it isn't part of a series.

+1 Anathem (2008) by Neal Stephenson

+1 The Speed of Dark (2002) by Elizabeth Moon

SF doesn't get much harder than The Martian by Andy Weir. It's about an astronaut's efforts to survive while stranded on Mars after a failed mission. All the science is plausible.

I can also recommend The Risen Empire duology by Scott Westerfield for realistic space battles.

How about The Expanse trilogy by James S.A. Corey? First book is Leviathan Wakes.

It is completely sci-fi, but has a lot of horror elements.