I started watching him when he had his oddly-timeslotted 10am morning show, with Edwin Newman at a little news-desk. The show was a successful failure in that even the suits at NBC could see that Letterman's gifts were suited for something around a later hour.
Given that late night show, Letterman was able to focus his sarcasm and self-deprecation to reinvent the talk show format as a sit-com, totally irreverant and brash. The first night (along with Bill Murray), he had home-run king Hank Aaron on - after the chat at the desk, a faux-sportscaster interviewed Hank on his reaction to the interview. That show, and the eleven years that followed, could very well mark the invention of the hipster era with its smart-alecy break-the-fourth-wall meta-consciousness
Letterman was also the best interviewer of the talk show circuit (Jay Leno, sorry, can't even do a good interview on his autoshop web-site), but he always made sure to followup any star with his own talk-show-about-nothing wierdness. Let's do a pretend Top-10 list! Let's drop watermelons from a crane! Let's do anything but take this seriously! Next up, a man-on-the-street interview with Larry "Bud" Melman!
Brush with greatness: When I worked in midtown Manhattan in the early '90s, I tried to get standby tickets to his show, never made the cut. Then, after he left NBC (and I loved the TV movie The Late Shift about this), I was walking down Broadway past the Ed Sullivan theater when someone passed out tickets to his new show. It turns out that I was able to see his very first rehearsal show for the new CBS timeslot. (Guests were the great David Brenner, The Blues Travellers).
The next week, I was on vacation in the wild backwoods of Maine, and had to watch the premiere show while sitting next to a 13" black-and-white TV, holding the rabbit ears the whole time in order to juice up the reception. Take that, you fancy-pants internet noobs.
So what happened? Some of it may be that the rest of the culture caught up to his shtick, so what was once irreverent just became grouchy. But for all that, he seemed to stop trying. Rather than being wide-eyed with wonder that he got away with antics, it was too hard to pretend that he was anything but hugely successful. The glitz of the tiffany network undercut his performance, and he began to phone it in.
Nothing can compare to the king, Carson, but Letterman had, at least, a great decade and a lasting influence. None of the current crop – your O’Briens, your Fallons, your Kimmels – would be here without Letterman. (Conan came close, but Kimmel may get the nod now).