Like Mike, I'm a fan of Elric. You want non-neat endings? Try the albino prince of Melniboné. I've got the Doubleday hardback two-volume set, and it rules.
Joseph also mentioned China Miéville...his Bas-Lag books are all good, but the best is the first,
Perdido Street Station.
American Gods has also been mentioned...big love for that, my fave Gaiman.
Looking at my bookshelf, I recommend:
Nuklear Age by Brian Clevinger...this is the guy who does the 8-bit Theater webcomic (
http://www.nuklearpower.com). It's essentially a novelization of a series of comic books. It starts off with slapstick humor, but it changes pace. Oh yes. It changes pace.
The Memory, Sorrow, and Thorn series by Tad Williams...these might fit your bill, fathead. Those books are
The Dragonbone Chair,
Stone of Farewell, and
To Green Angel Tower. Not a clean ending, and the author does a great job of playing with your expectations of Standard Heroic Fantasy, mostly by throwing out a few curveballs.
If I could write, I would want to write like this guy.
Solaris by Stanislaw Lem...kinda on the depressing side. It's been made into two movies (one Russian and one with George Clooney), and I think I stand alone when I say I liked them both. Lem leaves a few things unanswered, and it's of the science fiction family where they really go into the science, so it may be dry at times, but I immensely liked the story.
The Hot Zone by Richard Preston...real-life story of an Ebola outbreak in Reston, VA. A quick read, and kinda scary in a real-life sense to boot.
Lord of Light by Roger Zelazny...most people know his Chronicles of Amber, but I vastly prefer this sci-fi tale of science-made gods. The back of the book says it all: "His followers called him Mahamatsamatman, and said he was a god, but he preferred to be called 'Sam,' and said he was a man." This book has a lot of badass things hinted at than made explicit, like my all-time favorite Mother of the Terrible Glow.
Homicide: A Year on the Killing Streets by David Simon...back into the real world, a Baltimore Sun reporter spends a year tailing the Homicide department of Baltimore. It's...unforgiving and real...best describes it. This was the basis for one of my top five favorite TV shows of all time, Homicide: Life on the Street.
The Alienist by Caleb Carr...historical fiction turn of the century New York City, a serial killer on the loose, a specialist in the budding field of psychology - an 'alienist' in the parlance of the time - assembles a team to profile and track the killer. Gruesome, a little melancholy, but a great read. Avoid the sequel.
Ancient Evenings by Norman Mailer...a complete head-trip story within a story within a story (I think) within a story that loops on itself and has a skewed narration. A bit on the adult side from time to time, but a great launching point for any Egyptian-flavored scenario.
Aztec by Gary Jennings...like
Ancient Evenings, but with Mesoamerican cultures. A story within a story, told by an Aztec to a Spanish friar, of his people.
The True History of the Conquest of New Spain by Bernal Díaz del Castillo...English language translation of the conquest of Mexico by one of the conquistadores. His accurate portrayal of events has been lauded, and his version is the definitive one (as opposed to that of Cortes, who padded his with self-aggrandizing lies).