@Barton dug your whole list, listened to Art Tatum for the first time in a long time, because of it. Listened to "She's FUnny Taht Way", Sweet and Poignant...
@Deathshatner: couldn't really get into Mose Allison. Some of the stuff was good sure, listened to "Gettin' There" and but I don't know, didn't FEEL it, ya know? But then I heard "Young Man" a Who cover, I really dug it. It's more intimate and not so hokey.
Those are the two I didn't see listed that needed to be. Sonny Rollins is a well accomplished jazz tenor player from 60s and on, sort of the next wave after the popular greats. Alice Coltrane is the most messed up stuff you'll ever hear. She played harp, and the stuff is super crazy. Hard to explain. Lester Young was the prime bop sax player that the Beats listened to.
Albert King played smooth, soul inspired blues music in the early 70's. Hound Dog Taylor played a hard shuffle variety of the blues, really causes a ruckus when I listen to it.
Anything on Chess is worth noting, and Alligator has a pretty solid line up - even the stuff they put out today.
When I was still a moderately angry young man I used to think bossa nova was pointless and boring. I was a very, very stupid boy. Sure it's smooth and easygoing, but there are times when that's exactly what you should be. Also, the whole "let's remove the percussion from samba" was apparently a pretty punk thing to do.
If you are looking for rural acoustic blues, I think one the baddest of the bad is the Reverend Gary Davis. The guy was a commanding singer, killer guitarist and about every one of his tunes sounds like the apocalypse going down. He recorded much later on than guys like Skip James or Robert Johnson etc, so the fidelity on his recordings is often excellent especially on 50s tunes.
John Lee Hooker is really amazing, his music is really hypnotic sounding. If you are looking for some more recent blues that has a real hypnotic sound you could look up some Junior Kimbrough. Kimbrough's records are recorded in the 90s, but they are like some total time warp music.
Jazz is a pretty wide lake. Louis Armstrong doesn't sound a bit like Weather Report which doesn't sound much like Ornette Coleman or Duke Ellington or Sonny Sharrock, but they are all jazz. Get a library card and just try a bunch of the big names and move on out. You might have to dig in for a while to figure out what styles within jazz you like. I started with the fusion stuff, but the other stuff I like is a bunch of late 50s to mid 60s stuff in between hard bop, modal jazz up until everything went all free jazz.
There is all sorts of stuff already listed here that is worth hearing.
I was listening to Bill Broonzy the other day and he has a duet with a woman whose lines go something to the effect of, "You can play with my pussy, but oh treat that pussy right." Which leads me to believe that Big Bill Broonzy is the original Ol' Dirty Bastard.
Also since Charlie Patton gets a mention I'm going to toss in my own diverted rivulet: Cajun music. Rounder put out two comps called Louisiana Cajun French Music from the Southwest Prairies which have some of the most emotive, amazing music. (It's almost all accordion and fiddle music too, which makes me happy as I am a huge fan of instruments that other people find to be totally fucking irritating see: my irrational love for Neurosis' "Times of Grace" record) Anyway, Edius Naquin has a bunch of songs on the first record that are just mind blowing.
Also as far as oldie von moldies go:
Bix Biederbecke the Harlem Hamfats the Charleston Chasers/Red Nichols
I don't get that into new jazz (nu jazz) but here are a few shows I've seen that I enjoyed: Roy Hargrove and Hardgroove Josh Redmond MMW Aldrich Hansberry Quintet
Also, here's a plug for a guy with whom I play shows who I think is a pretty fucking incredible blues musician, his name is Charlie Parr and you can find his stuff here
Yay jazz and blues!! Yay yay yay yay! I teach swing dancing classes, so I particularly love anything that makes me want to dance, which ranges from hot jazz from the 1920s to small jazz combo to soul, r&b, funk, and boogaloo from the late 60s/early 70s. Love it. LOVE IT.
Pretty much all of my favorites have been mentioned here, so I'll just add on a couple that people may not have heard of -- The White Ghost Shivers - they're what happens when a bunch of punk musicians who likely indulge in various substances turn to hot jazz/western swing/dirty blues/hookum while putting on a kick ass show. They have a 7 foot tall ukelele player who also plays the nose-flute and tap dances (actually, the 7 foot tall dude is a friend of mine).
Sharon Jones and the Dap-Kings - If you like soul/r&b/etc from the 60s and 70s, you'll like these guys...they are the real deal. Sharon Jones used to sing back up on a lot of those records back then, and I believe most of her band are also musicians from that time. I think they use the recording techniques used in the 60s and 70s too, to get the real sound.
And lastly, this video is pretty kick ass as it features the fabulous bluesman Sonny Boy Williamson II playing the harmonica - like he's smoking a cigar!
Amazon is offering Coltrane's My Favorite Things, my personal favorite Trane, for download for only 99 cents today. If you don't already have it, I can't think of a better time to get it!