Yep. Headhunters holds up extremely well, and it is easy to get into whether or not you have a jazz background. Not really in Taxi Driver territory, however (for that I would second the Miles Davis soundtrack to Ascenseur pour l'échafaud).
You might throw Julius Hemphill and Jackie McLean in the mix, too. Maybe not the first jazz records to get into, but definitely a good entry point into some killer, but "difficult," post-Coltrane weirdness.
As someone who's primarily a rock fan, Art Blakey also pushes a lot of the right buttons.