Mrm. I think a lot of Gaiman's rep comes from his run on the comic book, The Sandman. You can collect 'em in graphic novels--they run the gamut from horror to mythopaeic fantasy, wherein gods and faery tale figures rub shoulders with ordinary people on a regular basis. Pretty good stuff, and a definite change of pace for the industry at the time, which was saturated with superheroes. The indy comics hadn't really picked up at that point, so for a lot of people, Sandman is groundbreaking.
I think Neverwhere is his best novel to date, followed shortly by Stardust and Anansi Boys in a too-close-to-call tie....
I myself wasn't much for American Gods, but my BF, who is a big Odin fan, loved it.
There's also a YA book, Coraline, which left me a little cold, not being Addams Family enough for me, and which is essentially Mirrormask Mark I.
Also, there is a kid's book, The Day I Swapped My Dad for Two Goldfish, which is awesome.
Good Omens, a book he did with Terry Pratchett, is very good, although sometimes people who are fans of either Pratchett or Gaiman, but not both, are turned off by the mixture of the two. It's a very funny Apocalypse story. Maybe not everybody's cup of tea.
This is what I've read, and the mileage varies for me. There are some people who rave about his short stories, none of which I've read. And
