[msg]

Not for every reader but Stephenson's Baroque Cycle (Quicksilver, The Confusion, The System of the World) is something between historical fiction and science fiction. Worth a try in your case.

Also, it's hard to go wrong with the yearly Hugo Award winners and nominees. Sometimes they are middle entries in long running series, which is worth checking on Wikipedia if you like to start at Book 1. Usually it is just going to mean the whole series is great.

How about a few great authors who have all won?

  Ursula K LeGuin
  Lois McMaster Bujold
  CJ Cherryh
  Connie Willis
  Jo Walton