YES on American Gods. I liked Anansi Boys, too. And if you can track down "Monarch of the Glen" (it's the last story in Fragile Things), it's a short story concerning Shadow. Also Gaiman's short story "Shoggoth's Old Peculiar" is pretty hilarious. (It's contained within Smoke and Mirrors - more-or-less it is Dudley Moore and Peter Cook as acolytes of Cthulhu.)
One of my most favorite books is Douglas Adams' Last Chance to See. It is nonfiction, the documentation of several trips to remote locations to find endangered species in the wild. Over the last twelve years I must've read my copy twenty times, and it still makes me laugh aloud.
Terry Pratchett is another of my favorite authors. His (non-Discworld) novel Nation is excellent. Don't be intimidated by the colossal number of Discworld novels, either - with very few exceptions (the Tiffany Aching books, for the most part) you can jump in anywhere you like. Although the novels share a common setting, there is rarely an overarching plot that you'd miss out on. That said, the Tiffany Aching books (in order, The Wee Free Men, A Hat Full of Sky, and Wintersmith) are some of Pratchett's best writing. I have an illustrated copy of The Wee Free Men that I'm saving to read with my oldest daughter...at her current reading rate, probably we have another two years to wait. Other Discworld novels I would recommend: Reaper Man, Small Gods, Hogfather, Night Watch, and Thud! Oh, and if you are a fan and happen to have toddlers around, do your sanity a favor and get Where's My Cow? Yes, a Discworld picture book. Oh, right, you said no fantasy. Well, crap, Nation fits, anyway.
OK, here we go. I also enjoy military history, and to this end I will recommend The Killer Angels, by Michael Shaara. It's about the Battle of Gettysburg, and if you enjoy it, you can delve into the books that Jeff Shaara (Michael's son) has written, listed here in order of historical conflict, NOT in the order written: Rise to Rebellion and The Glorious Cause (the American Revolution); Gone for the Soldiers (Mexican-American war); Gods and Generals (Civil War pre-Gettysburg); The Last Full Measure (Civil War post-Gettysburg); To the Last Man (World War I); The Rising Tide (World War II, Europe and Africa, pre-Operation Overlord); and The Steel Wave (Overlord to V-E day, I believe, I haven't read this one yet). [EDIT 7/21/09 - I have read The Steel Wave now, and it's really focused on Overlord plus about three months: the last events it details are in September 1944. There's a third novel coming out that details the final year of the WWII in Europe; following that I'm sure he'll do something similar for the Pacific Theater.] These novels are all American-centric - even though the novels also include British and German POV characters, the novels are focused on the US involvement in that conflict.
