A few more ideas:
The Cyberiad, by Stanislaw Lem
Mortal Engines, by Stanislaw Lem
The Star Diaries, by Stanislaw Lem
A Perfect Vacuum, by Stanislaw Lem
Imaginary Magnitude, by Stanislaw Lem
Fiasco, by Stanislaw Lem
The Futurological Congress, by Stanislaw Lem
War With The Newts, by Karel Capek
The Dying Earth series, by Jack Vance (more fantasy than science fiction but monolithic in terms of importance and plain old reading fun)
The Demon Princes series, by Jack Vance (the "demons" are interstellar criminals, not demons, if that matters)
The Stainless Steel Rat series, by Harry Harrison
The Deathworld series, by Harry Harrison
Bill The Galactic Hero, by Harry Harrison (a picaresque sci-fi comedy adventure based on "The Good Soldier Svejk"; contains a passing reference to a house of prostitution but is otherwise unobjectionable)
The Chronicles of Amber series (much more fantasy than sci-fi), by Roger Zelazny
The Uplift series, by David Brin
G�del, Escher, Bach: an Eternal Golden Braid (not exactly sci-fi but includes fiction and essays on science), by Douglas R. Hofstadter
The Mind's I (more thought-provoking essays that include sci-fi), edited by Hofstadter et al.
