haven't seen any guitar nods: check out django rheinhardt, les paul, and wes montgomery (in that order, chronological)
you need a good male jazz vocalist, start with chet baker. also check out mel torme.
these albums are must haves to go with kind of blue:
coltrane - a love supreme, blue train, my favorite things
miles davis - sketches of spain, miles ahead
dexter gordon - go
sonny rollins - saxophone collossus
mingus - mingus ah um
charlie parker and dizzy gilespe - bird and diz live at carnegie hall
clifford brown & max roach - clifford brown & max roach
duke ellington and louis armstrong - the summit master sessions
stan getz and joao gilberto - getz / gilberto
count baise - april in paris
herbie hancock - Empyrean Isles
you may want to jump start your collection with some compilations, you can figure out what you like from there and build more. here are some good boxed sets with links to buy at amazon (these three alone will set you back a few hunnie, but they're well worth it):
smithsonian collection of classic jazz
the verve story 1944 - 1994
ken burns' jazz collection (from his pbs show, heavy on swing, light on later stuff)
there are also great box sets out on the greats. check out the rca recordings of dizzie gilespe, the complete hot five and hot seven sessions of louis armstrong, billie holliday, sarah vaughn, bix beiderbeck, king oliver's creole jazz band and more.
if you want modern stuff, check out both branford and wynton marsalis -- their side men are all putting out wicked stuff. wayne shorter is still cranking too.