Kind of Blue is a phenomenal album, but for as much fanfare as it receives, I don't necessarily recommend it as an intro to Miles. It's an album that's not really indicative of any other work he's ever done, and as many jazz purists will argue, It's a Miles Davis album in name only. Bill Evans carries the album from start to finish along with John Coltrane.
If you're trying to transition from rock to jazz I definitely recommend Bitches Brew. Despite the fact that it's a fusion album, it's the fusion album and doesn't fall into the tired and dated cliches of every other album that was inspired by it. Miles' trumpet playing is also showcased a lot sweeter on BB than on Kind of Blue.
If you're ready to dive head first into the jazz rhetoric without caution, I definitely recommend Round About Midnight, Milestones, and the four Miles Davis Quintet albums (Workin' With..., Cookin' With..., Relaxin' With..., and Steamin' With..., respectively).

Well wasn't the distinguishing element to Kind of Blue was that it was the first album to feature modal, rather than chordal scales? I never developed a full appreciation for the album but perhaps it's because he was still early in his career.

I definitely agree with you about Bitches Brew, it's a fantastic album from both historical and artistic standpoints. And you can't downplay John McLaughlin's influence in the final sound, I think his guitar work on it is among the most impressive of his career.

I've always seen some of Miles Davis' more experimental work as the most easily accessible, in particular Sketches of Spain. Though the ties to jazz elements are tenuous at best, the melodies are wonderful, and Gil Evans' arrangement was top notch. "Concierto de Aranjuez" may be one of my favorite Davis tracks ever, the first five chords alone especially poignant.

Notwithstanding the fact that modal systems of play had been making their appearance in jazz records here and there prior to Kind of Blue, it was really Coltrane who brought that influence and style to the recording, and one way to really distinguish between Adderly and Coltranes's solos on the album is to listen to that Non-linear modal quality that a lot of Coltrane's licks have. It definitely did introduce the world to an unconventional style that of course was not recognized as being modal or anything else other than phenomenal.
What's most impressive to me about the album is Bill Evans ethereal piano work, the way it carries the band so beautifully and unobtrusively without calling any attention to itself. I've spent many spins focusing entirely on his piano work and he's definitely the unsung hero of that album.
I definitely agree with you here, I love Sketches of Spain and Concierto de Aranjuez. A Tribute to Jack Johnson is another one of his more experimental fusion-esque albums that gets swept under the rug in favor of some of his lesser works, but when you take a look at Davis' career as a whole, everything he did was experimental. The man has created more sub-genres of jazz than most jazz legends have albums in their discovery. Half of Davis' output was material that set the listening world on its ear, which is a reason why, of all his skills, I consider him a composer first, a band leader second, and a trumpet player last. That's far from saying that he hasn't any skills on the horn, far from it, it's just that the foundation of his legacy is really built upon his musical creativity and his ability to lead a group toward a unified musical vision.

Kind of Blue is the perfect 'company for dinner' album. I can only guess how many hundreds l've times I've listened to it but it somehow doesn't become unlistenable. That's a rare quality in any album, let alone a jazz one. Bitches Brew, on the other hand is unfortunately on my list of overplayed albums. I haven't heard it for years and I'll go a while longer. The good news is that one day I'll get to hear it fresh again and it will reignite my passion for that kind of thing.

My personal favorite Miles album is Filles de Kilimanjaro. It was made only a little while before Bitches Brew and it has kind of the same feel but with more Miles and before he had gone electric. I think of it as his acoustic pre-fusion. This album I can listen to pretty much any time any day. Very accessible but still experimental and interesting.

Wes Montgomery's The Incredible Jazz Guitar of.... has always been my favorite for that purpose.

It's also good for summer days on the porch.

I can't help but notice no one has mentioned the semi-live album, Live-Evil. It was post Bitches Brew, so naturally, that fusion sound is there, but it's a masterpiece of its own. It definitely holds a spot in my 5 top miles albums. My passion for this album is kept alive through a nebula of a familiar sounds and hearing sounds I didn't notice before. Unlike most of his work, though, I don't feel like it was ahead of its time. It was right there in the peak of it all. There are evident elements of Sketches of Spain, and for that alone, the album fogged me with nostalgia the first time I ever heard it. I believe this sound comes from his collaboration with a Brazilian composer, whose name I'm uncertain of right now. "Sivad" is a great opening track. The song sets the mood for the album instantly. Like a book, the album takes you to another place. Each song is a chapter, telling a story you've heard many times before, but never mind hearing again.

I had to bump this to tell a funny story.

So, after all the rave about Live-Evil, I had to put it on. I threw it on the record player while I hopped in the shower. I was watching my roommate's kid at the time (he's six), and I left him in the living room with some video games. Moments later, I hear a tap on the bathroom door. As tiny muffled voice says, "Uh, Caaatthy? What's that noise? It sounds funny." I didn't know what he was talking about so he repeated, "That noise is coming from your room. It goes wahhhhhh, waaahh." I poked my head out of the shower to tell him it was Miles and was immediately faced with a terrified look on his face. He didn't leave my side for the rest of the night.

I just tried King of Blue myself and I must say..I'm pretty impressed; awesome work.

Thanks guys!

Where's the love for Birth of Cool?

The real thing about Miles is that he was at the forefront of every development in Jazz during his time.