I know why Mark suggested that I read the "Book of the New Sun" series by Gene Wolfe. (It's a tetralogy, printed in two volumes: Shadow and Claw and Sword and Citadel.) It's the kind of book that makes you immediately want to talk to someone who's read it, or grab the lapels of strangers on the train and say "Have you read Gene Wolfe? Read Gene Wolfe! Read Gene Wolfe!!" There are a few other mind-bending books I'd put in this category -- Infinite Jest, Gormenghast, and House of Leaves come to mind. The Book of the New Sun is an extraordinary work: a bildungsroman, a philosophical and religious meditation, a science fiction novel set thousands of years in the future yet with a medieval feel, a quest, a puzzle. I would have to write a very long review to do it justice. Instead, here's a brief list of authors that these books share an affinity with: Kafka, Borges, Ursula K. LeGuin, Joseph Campbell, Mervyn Peake, Dickens, Pynchon, The Brothers Grimm, Mary Shelley. This isn't "literary science fiction," this is literature.
There's a sequel, The Urth of the New Sun, which is next on my list. Incidentally, I picked up another Gene Wolfe novel, Castleview in a used bookstore for three bucks. Make sure it's the last Gene Wolfe book you ever read, because it's very disappointing. Well, they can't all be masterworks.