Personally, like your suggestion for Gaiman, I highly recommend anything written by Roger Zelazny.

If you enjoy the Chronicles of Amber, you might also enjoy Jose Farmer's World of Tiers series. Along a similar vein but dissimilar enough that it's worth the read.