My favorite novel of his was Peace which was marketed, I believe, as mainstream, and so can be hard to find if you stick to the sf section. It was about a person suffering from (probably) Alzheimers who was wandering around his house and his life at the same time. Wolfe is at his best when he is dealing with the nature of memory and how that relates to reality.
He is best know for his series "The Book of the New Sun" which is four books -- The Shadow of the Torturer, The Claw of the Conciliator, The Sword of the Lictor and The Citadel of the Autarch. That's probably a good place to start.
His prose is very dense, and some days I absolutely adore it, and other days I can't stand it. So if you have a hard time getting into him, just set it aside for a bit and give it another try later.