Yeah, I am kind of in the same boat, really like some jazz-influenced work but not all that into jazz per se. Agree with easy, the more what I would call approachable jazz that truly is jazz would be Miles Davis. He's definitely jazz yet more melodic and relatable than most.
Brubeck Time Out is really an exercise in time signatures. (Time Out is a play on time, each cut using a different unusual time signatures like 9 8, 6 4, 5 4, etc.) I wonder if it would be so popular if it hadn't been used in so many movies....
Charles Mingus, (Mingus)4 is a monster. And not sure if the jazz officials will call it jazz for sure but if they will then the kings of listenable jazz are Satchmo and Duke.
Ellington Jazz Party in Stereo and Satchmo Plays King Oliver are awesome music and bona fide audiophile classics.