Five CDs I would give an aspiring jazz fan:
Charles Mingus, Mingus Ah Um
Dexter Gordon, Our Man in Paris
Wynton Marsalis, Black Codes (From the Underground)
Bill Evans, Riverside
Duke Ellington, Ellington Indigos
(Yes, I know. But there’s plenty of time for Kind of Blue.)
My personal opinion is that you can’t go wrong with ANYTHING by either James Booker or Vince Guaraldi. (And yes, I know that’s a fairly odd pairing - but they are my two favorites!)
For the OP - Booker is a New Orleans pianist who will quite frankly blow yer socks off if you like jazz piano. Serious virtuoso, serious drug addict.
Guaraldi is the guy who wrote the piano music that you hear in all the Charlie Brown/Peanuts cartoons. But that’s not all he did - I love his style. Check out his greatest hits.
As long as you’re going to get the Miles Davis Quintet Workin’, Cookin’, and Steamin’, you might as well round it out with Relaxin’. All four albums were the result of two 1956 sessions in Rudy van Gelder’s studio in New Jersey.
Rudy van Gelder is a genius recording engineer whose output from the mid-'50s through the '60’s (at least) was always reliably superb. If you have an album in your hands that you want to know if it’s any good, look at the engineer on the back cover. If it’s van Gelder, you can’t go wrong.
Also, check out Benny Golson and Art Farmer with their Jazztet.
Claude Bolling and Jean-Pierre Rampal collaborated on some pretty fun records in the late seventies / early eighties. Look for Suite for Flute and Jazz Piano. If you like what you hear of Brubeck, especially his playing around with exotic time signatures, you’re sure to enjoy these guys.
Arrangers can also be a useful bellwether for quality product. A few names that are hallmarks of excellence are Fletcher Henderson, Neal Hefti (he wrote the title music to the TV version of Batman, so at least you’ve heard something of his, probably), Bill Holman, Nelson Riddle, and Quincy Jones.
Enjoy.
The Essential Duke Ellington gives a good overview of Ellington’s career - one of the longest and most important of any jazz musician/bandleader/composer.
Sidney Bechet is another early jazz musician worth listening to. He specialized in soprano sax (and also played clarinet, although not as often as the soprano). There are a zillion Bechet CDs out there - good collections include the Complete Blue Note 1939-1951 Master Takes and the Complete Original American Rca Victor Masters.
One CD set I really love is The Luis Russell Story. Russell was a Panamanian-born pianist who took over a band formerly led by King Oliver and turned it into one of the first swing bands. The transformation in sound is amazing - the band was years ahead of its time.
Another important early jazz band was Bennie Moten’s Kansas City Orchestra. This is the band that Count Basie more-or-less inherited when Moten died in the early thirties. Moten’s orchestra was the most important and successful territory band of its time. They started with a distinctive sound and later switched to an early form of swing (when Basie and others joined the band). You can hear most of Moten’s output on Bennie Moten’s Kansas City Orchestra, Vol. 1, Bennie Moten’s Kansas City Orchestra Vol.2 and Band Box Shuffle.
I agree with those who say listen on the radio and find your taste before you go out and buy.
And here’s an amusing (though evidently untrue) aside regarding Thelonious Monk:
The Loneliest Monk article @ All About Jazz
(snicker) That’s always cracked me up.
Miles Davis is always a good place to start - but before “Kind of Blue”, I’d recommend “Miles Ahead”. It’s Miles playing flugelhorn with a 19 piece group, and has some fantastic tunes - “Springsville” is one of the most incredibly uplifting pieces of music you’ll ever here. “Blues for Pablo”, “My Ship”, “The Duke” - tons of great stuff.
“Seven Steps to Heaven” is also really accessible (and under-rated) Miles with some great blues playing on it, and the remarkable debut of Tony Williams, who spices some of thetracks up nicely
Bill Evans is a remarkable player - his music is complex and lovely - I listened to it a lot as a jazz newbie and it got me used to complex melody and harmonisations.
Cannonball Adderley is a mixed bag -he’s enjoyable enough but some of his later music is a bit simplistic.
Be very wary of John Coltrane. If the cover picture shows him holding a soprano sax - run far, run fast. Actually, this is pretty good advice for any soprano sax players.
Avoid at all costs - Ornette Coleman, Pharoah Saunders (guaranteed the WORST music you will ever hear), Jimmy Guiffre and Alice Coltrane
Good luck and please keep us posted on your growth as a jazz lover!
mm
What, no Ella fans?
Get some Ella (that’s Fitzgerald). In particular Ella and Louis.
Female vocalists Billie Holliday, Sarah Vaughan, Carmen McRae, Betty Carter, Shirley Horn, Terri Thorton and Dianne Reeves.
Sample the late Terri Thornton in “I Believe in You.”
It’s useful to divide Coltrane’s career into 3 separate categories: his career as a sideman with such names as Dizzy Gillespie, Miles Davis (Kind of Blue) and Thelonious Monk (Thelonious Monk With John Coltrane), his mid-career as the leader of his own trios and quartets (Blue Train, Giant Steps) and the last couple of years of his life where he went completely avant-garde with chaotic experimental free jazz (Kulu Se Mama, Meditations). Personally, I find much value in all stages of his career and I find Kulu Se Mama, in particular, to be one of his most intriguing.
Or, on the other hand, they might just be among some of the most provocative and challenging voices in jazz. Granted, free jazz is definitely not for everyone but it can be rewarding for anybody who’s willing to make the effort. Of course, it’s a big plus to have a solid grounding in jazz fundamentals to aid in understanding this genre. Other artists in this vein include Charlie Haden (Ornette Coleman’s bass player), Don Cherry and Sun Ra and, more recently, John Zorn’s '80s-'90s work with Naked City and Marc Ribot’s work with Shrek.
It seems that Miles Davis rings a few bells around here. I’m going to start there. Thanks ya’all and I’ll try to keep you informed.
That’s cool 
Just remember that if you don’t like him, it’s only one style of jazz he’s playing, and there’s much more to choose from.
Thanks for posting these, CtM. Wonderful vocalists each and every one of them.
Every musician on my list has been mentioned in this thread. I just wanted to mention that I’d rather scrub the whole house with a worn-out toothbrush than spend more than 10 minutes listening to Diana Krall. She bores me to tears, yet she has a knack for hiring good musicians to play with her. Enormous irritation level here.