Every new "fairy tale for adults" is inevitably compared to Goldman's The Princess Bride. Stardust, though it's already received such comparisons, doesn't really deserve them. Where Goldman told his fairy tale in a detached, self-aware way, Gaiman tells his story straight up. Stardust lacks the developed irony that pervades Goldman's work; instead, it possesses a light charm and an authentic feel all its own. If The Sandman is Gaiman's "Hamlet," then Stardust is his "Midsummer's Night Dream." It is less ambitious than his masterpiece, but no less brilliant. (I ought to note that there are two versions of this book: a handsome Vertigo edition with 175 illustrations by Charles Vess, and a standard Avon version without the pictures. I highly recommend the Vertigo edition, as the pictures add immeasurably to the atmosphere of the book.)
Up until now, Gaiman's prose novels have been small works -- Stardust is a light fairy tale, and Neverwhere is a small urban fantasy. They're good books (Stardust, as those who can remember what I wrote a paragraph above, is in fact excellent), but they're not on the epic scale of Sandman.
Neither is American Gods, not quite; but it's definitely in the same league. This is most definitely a book from the author of Sandman -- it displays the same erudition and deep knowledge of myth, the same interest with how mythological figures would interact with the modern world, the same skilled prose, the same knack for memorable characters, and the same deft plotting. The plot was perhaps the most surprising element of this book: throughout the book, I found myself growing irritated with small, but noticeable, gaps in the backstory, and was convinced that Gaiman had tried to shoehorn in a weak plot to explore a theme he was taken with. So I was absolutely delighted when... don't worry; I won't give away the ending. But I will say that it's best to suspend judgment on the plot until you've finished the book. This is good stuff, and anyone who's been wishing that Gaiman would try his hand at something similar to his Sandman stories just got their wish.
First things first: These are graphic novels, but don't you even think about not reading them for that reason alone. While I'll be the first to agree that most comic books are pretty bad, The Sandman isn't most comic books, and it'd be silly to condemn it for the sins of a genre. In fact, The Sandman is a spectacular work of epic fantasy, informed by a broad knowledge of mythology and a superb grasp of humanity. With a fascinating and fully-realized setting, a whole cast of interesting characters, and a plethora of plotlines which all tie up neatly into a grand arc, Gaiman has managed to make his surreal dream-world into something very real indeed.
Don't be misled by the fact that I've put these two books together here; they're not a series, and they have nothing to do with each other, except insofar as both of them are historical/legendary novels. Sherwood is Godwin's retelling of the Robin Hood story. Rather than setting it during the Crusades and Lionheart's reign, however, Godwin sets it in the Norman Conquest. The result is a familiar tale that's freshly told. Firelord is an Arthurian novel set at the end of the Roman rule of Britain. Again, Godwin brings new elements to a familiar story. The result is one of the best Arthurian novels I've read yet.
A few seconds ago as I write this, I went to add a review for The Silent Gondoliers, figuring that I'd plug it in right under the review for The Princess Bride. It was something of a startlement to realize that I'd somehow never gotten around to writing up a review for The Princess Bride. That's a problem easily rectified, at least.
I don't feel that I need to say a lot about this book, since most people have probably seen the movie based on it, and (since Goldman wrote the script for it) the movie is astonishingly faithful to the book. But just in case you haven't seen it, a brief description: it's an adventure story, with swordfights, castles, evil princes, beautiful princesses, and true love; all of which is bracketed by a framing story purporting to be about the author's life -- all very self-referential and post-modern, but without being overly precious. The framing story in the book is one of the few places where the movie greatly deviates from the book -- the movie's framing story is a bit saccharine and sweet, while the one in the book is borderline cruel. But it works, all of it; good stuff.
Like The Princess Bride, this book is a sweet little story that plays meta-fiction games (S. Morgenstern is the purported author of both books, for instance). Here, though, the story is smaller, both physically (the book is about 100 large-print pages) and conceptually. This isn't a grand swashbuckling adventure -- it's a fable, a just-so story explaining why the gondoliers of Venice no longer sing. But, as ever, Goldman's writing is reliably charming, amusing, and insightful.
I've always found mythology to be fascinating -- back in sixth grade, before I was even reading SF, I devoured every book on the topic in the school library -- and I've always found Norse mythology to be the best of the lot. In Rhinegold, Grundy masterfully retells the saga of the Volsungs. The book is truly epic in scope, with a cast that spans generations; pay attention to that family tree in the front, because you'll probably need to refer back to it a few times. Most importantly, though, it has a very authentic feel to it: one imagines that this is what it would really be like to live in the Scandinavia of the sagas.