Neil Gaiman is without a doubt one of the greatest living authors. If you haven't read Good Omens (written with Terry Pratchet) DO IT NOW! It's the best irreverent novel concerning the biblical apocalypse ever (okay, maybe the only one, but that doesn't negate its greatness).
If you're going to read American Gods, I say do it right and read the author's preferred text. You can find the limited run British one used online or wait until this summer for the 10th anniversary re-release. It has more than 12,000 extra words that were cut to control length.
I also recommend Sandman to anyone with an interest in mythology, literature, and weirdness. Even if you never thought you'd like a comic book, you'll like this one.
It was great. Neverwhere was really excellent, too, as far as his novels. It created a very dark and compelling world and atmosphere.
Don't forget to read the follow up book called "Anansi Boys"