I definately second Jahn's recommendation for "Time Out". Great Cd in all ways.
I suppose there are many different ways to start off in jazz depending your musical background and tastes. Some people, including myself, like to start off with a little bit more melodic jazz.
Following this direction, I would recommend Stan Getz and Joa Gilberto with the CD "Getz/Gilberto", which has smooth melodies paired with samba rhythm.
Another suggestion for a relatively melodic Cd is Charlie Haden and Pat Metheny's "Beyond the Missouri Sky". Charlie Haden plays acoustic bass and Pat Metheny plays acoustic guitars. The songs are very spiritual, emotional, easy to listen to and, I dare say, without being superficial. This was also my first jazz Cd. (Edit: I didn't see that SunShip already recommend this CD. I'll just second his recommendation then)
Another great way to start into jazz is via vocal jazz. There are many great men and even greater ladies of jazz. Ella Fitzgerald is one example, although a little bit old-fashioned maybe. You could check out Diana Krall's "Live in Paris". It's a lot different from her more "commercial" Cds such as "The look of Love". Energetic and just a wonderful live performance. Another great ladies are Holly Cole and Cassandra Wilson. For Holly Cole, I would recommend "Don't Smoke in Bed" with the first song "I can see clearly now" being one of my favourite vocal songs. Cassandra Wilson's "Belly of the Sun" is a Cd, which, as the title already imples, makes you feel good. Her voice is very deep for a female singer but to quote critics: "She has a very wise voice".
If you liked the club atmosphere, maybe musical "energy" could be your ticket to jazz. If you are into piano: Try Keith Jarrett's "Köln Concert". It's a solo piano concert divided into 4 parts. The first and last parts are more lyrical compared to parts 2 and 3.
There are also a lot of great piano trios consisting of piano, bass and drums such as Bill Evans trio, Oscar Peterson Trio, Keith Jarrett Trio and many more. A lot of these trios start a song with its theme and start developing on it, which can eventually culminate in a musical climax. A jazz artist (whose name I can't remember right now) said that "good jazz is like good sex".
For trumpet, Miles Davis' "Kind of Blue" is always a hot pick although I prefer his "Birth of the Cool".
For sax, you should give John Coltrane a try. I found that Coltrane's "Lush Life" was the Cd, which most people without background in jazz could connect to the most easily (in Coltrane's repertoire that is).
Finally there's not definate way of how to start in jazz and it might be through the music you already like, be it hip hop, country, rnb, classic, electronic, etc. Starting with jazz classics might not always be the most ideal solution as sometimes, it's a lot easier to connect to a cd that is from the right time, which could be a cd that has been released just recently. For example, electronic pop has been quite chic here in Germany last summer and a friend of mine hence started his jazz journey with Bugge Wesseltoft's "Moving", which is a very modern, electronic and slightly melodic cd. Another example is Guru Jazzmatazz who has been successfully merging jazz with hiphop for a long time already. If you can tell us your musical preferences, that might help.
Finally, working your way through history as john_jcb suggested can be tiresome but also very rewarding in the end.
Here is another good site for information on jazz:
http://www.allaboutjazz.com/
