Charles Mingus - The Black Saint and The Sinner Lady
This is a religious experience.
But there are so many different types of jazz, it's hard to recommend things and not leave out something important. The best thing to do is just to dive in, find the sounds you're looking for, read about the musicians, the history, etc. I'm reading Miles Davis' autobiography right now, and I'm having a good time listening to his musical career in chronological order, and just skipping around. I love the second great quintet and fusion the most, from about 1963 to 1975.