Just found this thread and as a long time jazz fan, very glad to see others discovering this great music and getting it. (Especially the REAL stuff and not the "smooth" pop stuff.)
To me, one of the great things about jazz is that it's both a pure and mongrel art form. By that I mean, it's pure in a musical sense in that mostly it is making music for the love of music, not to be a star or get rich. But it's a mongrel in that there are so many different styles and sounds - and that gives the benefit that there are a lot of different entry points. Some will be immediately entranced by the iconic sound of a Coltrane, Monk, Mingus, Miles etc. but others may need to be sort of eased over to let their ears "tune up" a bit to the sound of jazz.
If you're into metal, there is some great fusion with awesome guitar playing by the likes of Allan Holdsworth, Scott Henderson, John McLaughlin, Dave Fiuczynski and many others. If you're used to vocals, there are of course plenty of great singers. I love a lot of jazz that includes influences from music around the world like African, Middle Eastern and of course the nearly as old as jazz itself Latin jazz sounds.
The fact that the history of jazz basically coincides with the history of recording music means that virtually the entire history is available on record, which can be pretty overwhelming and intimidating. One of the classic bits of advice to deal with this is to find a Miles Davis record and, if you like it, find out who played on it and look for records made by those guys. There's a lot of truth in this because of the way Miles never stood still musically and was at the forefront of half a dozen different styles, and at the same time was not just a great musician himself but one of the best talent scouts and never afraid to surround himself with incredibly talented people.