Sheri S. Tepper's _The True Game_.
_Three Hearts and Three Lions_. I forget who the author is, but this book was the inspiration for the D&D Paladin class. And it's a pretty good read.
_The Black Company_ series by Glen Cook.
I second Wolfe's _Book of the New Sun_, and Vance's _A Dying Earth_. Both writers present odd but plausible cultures quite well. If you do pick up _Book of the New Sun_, read it through once, put it aside for a day or two, and then read it through again, carefully. Pay attention to the words and try to visualize what is happening. Wolfe is wonderfully capable at misdirection and writing through a character's eyes, misconceptions and all...
_A Game of Thrones_ is popular, but the books are long enough that I'm having a hard time following the story, and I used to read through _The Lord of the Rings_ in an afternoon.
The Tir Alainn trilogy by Anne Bishop.
Aristoi, Metropolitan and City of Fire by Walter Jon Williams.
The first Amber pentology by Roger Zelazny. Lord of Demons, ditto. Heck, nearly anything by Zelazny.
C.J. Cherryh's Fortress series.
Tarek