- The Culture series by Banks
- Dune, at least the first book
Psycho paranoia classics:
- Anything by Philip K Dick, especially Ubik
- Solaris by Lem
1000+ pages of terraforming epic: Mars trilogy by KS Robinson
Hardest sci fi ever, a HN classic whenever cellular automata are discussed: Permutation City by Greg Egan
I read almost everything Egan published. While I love his work dearly, I've had very poor success with introducing people to his "alternative physics" stories (where he takes some law, flips a sign somewhere and rolls with the consequences [])... it's TOO hard. Not everyone likes a sci fi book that requires readers to follow along with pen and paper. So I always first recommend Permutation City, or maybe the short story collections such as "axiomatic"...