“I decided to go looking for my mother as a dragon.” – Peter from Necromancer’s Nine by Sheri S. Tepper
I enjoyed everything she wrote before 1989, especially The True Game series. Then she went all didactic about environmental issues. Then, starting with Grass, I started hating her books.
The Westing Game, by Ellen Raskin
The Godfather, by Mario Puzo
I, Cladius, by Robert Graves
“The man in black fled across the desert, and the gunslinger followed.” - The Gunslinger
Or is it too obvious?
Also more than one line, but still:
Once when I was six years old I saw a magnificent picture in a book, called True Stories from Nature, about the primeval forest. It was a picture of a boa constrictor in the act of swallowing an animal. Here is a copy of the drawing.
– The Little Prince, by Antoine de Saint-Exupery
Gravity’s Rainbow
I knew you weren’t paying attention.
That’s funny in a very embarrassing sort of way, ya know?
“We need you to kill a man”
-Robert A. Heinlein, The Cat Who Walks Through Walls
“When Augustus came out on the porch the blue pigs were eating a rattlesnake - not a very big one.”
Lonesome Dove, by Larry McMurtry
:dubious:
“I, Rikudo Koshi, hereby give my permission…” 
I second the opening for War of the Worlds.
How 'bout:
“The primroses were over.” from Watership Down by Richard Adams. Didn’t really appreciate it until I got to the end of the epilogue where the last sentence created a nice indirect cycle. This book also has one of my favorite all time last sentences (if you don’t count the epilogue):
“Underground, the story continued”. It just works on so many levels.
I always get the shakes before a jump.
Starship Troopers, Heinlein
“A Saturday afternoon in November was approaching the time of twilight, and the vast tract of unenclosed wild known as Egdon Heath embrowned itself moment by moment.”
Return of the Native by Thomas Hardy. Of course, it’s not just this opening sentence, but the whole opening chapter, that creates such a vivid sense of place.
“‘To be born again,’ sang Gibreel Farishta tumbing down from the heavens, ‘first you have to die.’”
The Satanic Verses by Salman Rushdie.
"My desert-island, all-time, top-five most memorable split-ups, in chronological order:
High Fidelity by Nick Hornby.
L. Sprague de Camp was always good for a killer opening line. He quotes two of his own in his Science Fiction Writer’s Handbook. I’m semi-quoting from memory:
“The way Smith got involved with the naked princess was like this…”
(Don’t recall the book)
and
“Sir Fitz-Hugh raised his visor and wiped the sweat from his brow under his helmet and continued riding his horse down the banks of the Hudson River.”
That’s from Divide and Rule, I think.
“You think you know how this story is going to end, but you don’t.” - Christopher Moore, Lamb: The Gospel According to Biff, Christ’s Childhood Pal
“All this happened, more or less.” - Kurt Vonnegut, Slaughterhouse-Five
In addition to the Joyce, García Márquez, and Austen already cited, let me add:
“The cradle rocks above an abyss, and common sense tells us that our existence is but a brief crack of light between two eternities of darkness.” Vladimir Nabokov, Speak, Memory
“For whom is the funhouse fun? Perhaps for lovers. For Ambrose it is a place of fear and confusion.” John Barth, “Lost in the Funhouse”
“In the beginning God created the heavens and the Earth.” Genesis 1:1
Good Omens by Neil Gaiman and Terry Pratchett
Or we have Pratchett by himself, in Lords and Ladies:
“In the beginning there was nothing, which exploded.”
He did! I found it here at 4.12.
(But what about the king?)
My contribution, from Don Quixote:
It’s the “whose name I do not wish to remember” that gets me.