Brad Mehldau, who does a lot of covers of pop/rock songs (e.g. Beatles, Nick Drake, Radiohead) - I'm not really sure what his best album is but Day Is Done is good with a pretty "accessible" tracklist.
Getz/Gilberto, which is in the top tier of classics, super easy to listen to, and starts off with an all-time classic song.
Sun Ra - Interstellar Low Ways or Visits Planet Earth. Ra's story, image and Afrofuturist/space themes make him stand out, and these both accommodate some of his idiosyncrasies while also being very accessible and fun.
Ella Fitzgerald - maybe the easiest to like of the most well-known jazz vocalists. I'd probably pick one of the albums on which she sings standards by A-list songwriters (Cole Porter, Gershwin, Rodgers/Hart, Ellington) and you could quite reasonably pick all of them.
Django Reinhardt - worth showing that jazz is not strictly an American genre, and his stuff is fun and easy to listen to. And anybody who likes guitar-based music should appreciate his ability.