Here are ten of my favourite science fiction books. Some are "classics", a couple are relatively obscure, all are highly recommended. Hopefully you will find something interesting you haven't read. It is not intended to be a comprehensive overview of the genre!
Kurt Vonnegut : The Sirens of Titan (1959)

Winston Niles Rumfoord falls into a discontinuity in space and finds himself materialising in his home town once every fifty-nine days. When he appears he makes predictions about the future which always come true. When he tells his wife she is going to Mars to mate with the rich and obnoxious Malachi Constant she is rather distressed.

Vonnegut mixes standard science devices ideas with more "literary" philosophical ideas. There are a few clunky moments where you feel the former aspect could have been better developed, but ultimately the result is brilliant. Malachi Constant goes to hell and back, but who is pulling his strings? The answer is bleakly comic, but Vonnegut's compassion for his characters shines through.

Further Reading: "Cat's Cradle", "Slaughterhouse Five"

Link: The Vonnegut Web

Theodore Sturgeon: E Pluribus Unicorn (1953)

A brilliant short story writer, his best work is scattered around numerous collections and anthologies. Still, these thirteen stories (covering 1947-53) are a pretty good introduction. "A Saucer of Loneliness" effortlessly twists flying saucer cliche into something strangely poetic. "The World Well Lost" is a humorous (and for the time daring) look at alien sex. This collection also includes horror and other genres, but Sturgeon's weird tales generally transcend these boundaries.

Link: Theodore Sturgeon

Walter Tevis: The Man Who Fell to Earth (1963)

An alien whose home planet is dying lands on Earth. He calls himself Thomas Newton and tries to be accepted as a human being.

A classic novel written with both intelligence and compassion. The brilliant film version is extremely faithful to the book (which makes a change). Tevis seems a bit overlooked these days, perhaps due to his small output.

Further Reading: "Mockingbird" and the short story collection "Far from Home" are both excellent.

Haruki Murakami: The Hard-Boiled Wonderland and the End of the World (1985)

One of the most popular writers in Japan, I think this is the only one of his novels you could really describe as science fiction.

The chapters of the book alternate between two seemingly unrelated narratives. In the first (realistic) section a man is involved in mentally coding and decoding information for his sinister company. In the second (dreamlike) section a man arrives at a town where unicorns roam the fields and men are not allowed to possess shadows.

Murakami's hero (in the first section) is cool and detached, and this style clashes nicely with the sci-fi elements. This in turn contrasts with the mysterious second narrative which is written with beautiful clarity. Admittedly the plot gets a bit slow a couple of times, and Murakami throws in way too many cultural references (Lauren Bacall, Ben Johnson, Charlie Parker etc. etc.), but the way the two plot strands come together is genuinely brilliant and unexpected.

Further Reading: "A Wild Sheep Chase" is like "Hard-Boiled Wonderland" without the sci-fi elements and is less impressive.

Link: The World Of Haruki Murakami

J. G. Ballard: Concrete Island (1974)

A man crashes his car onto a large traffic island surrounded by busy motorway. He is badly hurt, but no one comes to help him. He is too weak to leave and the island becomes his prison.

My favourite of the series of dark, cerebral sci-fi novels Ballard wrote around this time. Surreal, intense and disturbingly believable.

Further Reading: "Crash" is his most extreme novel, if you can stomach it.

Link: J. G. Ballard

Alan Moore: Watchmen (1987)

The Watchmen are a group of costumed "super heroes" who split up many years ago when the police clamped down on their vigilante tactics. Illustrated by Dave Gibbons.

If you haven't read a comic since you were 13 then this just might convert you to the 'graphic novel'. Moore manages to add serious and adventurous ideas to the format without neglecting the fun elements that attracted you to comics in the first place i.e. fast moving stories with plenty of action.

Further Reading: "V for Vendetta", "The Complete Ballad of Halo Jones"

Other Interesting Graphic Novels: "Rogan Gosh" by Milligan and McCarthy, "Murmur" by Mattotti and Kramsky

Gene Brewer: K-PAX (1996)

Prot, a man who claims to be an alien, is put into a psychiatric institution. He describes his utopian planet K-PAX in incredible detail to Dr. Brewer, who is becoming obsessed with the case. Meanwhile, Prot's presence seems to be having a beneficial effect on the other patients.

If Kurt Vonnegut wrote an episode of "The X Files" it might turn out like this. Brewer sustains the central enigma (is Prot really an alien?) brilliantly.

Link: Official Site

Walter M. Miller Jr. : A Canticle for Leibowitz (1959)

World War 3 kills most of the human population and turns much of the planet into a radioactive desert. Most blame science and technology for the war: books are burnt and "smart guys" are killed by the mobs. Earth reverts to the dark ages, but an obscure order of monks guard surviving books ("bookleggers") and study the life of Saint Leibowitz (a 20th century scientist).

One of the most original post-Apocalypse scenarios, this sometimes feels more like a historical epic than a science fiction novel. Recently ripped off by the TV series Babylon 5!

Harlan Ellison : The Beast that Shouted Love at the Heart of the World (1969)

Twelve stories (in the UK edition), mainly from 1968-9. Like Sheckley, Ellison is a master of the short story, but his vision is much bleaker (unbearably so in "Try a dull knife"). This collection includes the classic "A boy and his dog" in which a young man wanders through a post-Apocalypse landscape with his telepathic (and more intelligent) canine friend. More typical is "Asleep: with still hands", a weird yet haunting meditation on mankind's need to wage war.

Further Reading: "Deathbird Stories", "Spider Kiss" (the later is a novel about early rock 'n' roll)

Link: The Islets of Langerhans

Paul Voermans : And Disregards the Rest (1992)

Most of the cast of an outdoor Shakepeare production are killed in a bizarre accident. Years later one of the survivors (whose life has been a mess ever since) tries to find out the truth. Was it really an accident? Are aliens really trying to contact him or is he simply going mad?

Voremans' ideas bring to mind classic Philip K. Dick, and the hero's genuine doubt over his own sanity is brilliantly sustained. There is also a "novel within the novel", written by another of the survivors. This seems a bit overly clever at first but works well as the story progresses. Philip K. Dick is a good reference point but Austrailian Voermans has his own vision, partly shaped by his country's landscape. Perhaps the best recent sci-fi novel I've read.

Further Reading: "The Weird Colonial Boy". Voermans goes all out for comedy, but he isn't a natural at it. Still enjoyable though.