I cannot recommend enough Latro in the Mist, a combination of two of his novels about a Roman soldier in Greek times given the curse of losing his memory every day.

To me this was his most 'approachable' novel by virtue of the fact that I could cross-reference the names with historical resources like Thucydides -- I also highly recommend the Landmark series for their detailed annotations.

Fifth Head of Cereberus is, of course, the best way to start with him, and I re-read it every few years. If you have never read Wolfe before, I would start with Fifth Head. It will give you an early sense for whether Wolfe is your cup of tea.