It's been more than a decade since I watched Letterman, mainly because I don't usually stay up that late (although when I do I always stay for Craig Ferguson, since I was a fan back when he was still Bing Hitler), but I have so many fond memories.
One of my fondest goes way, way, way back to the early 1980's, the first time I saw Letterman. He did a parody of after school specials in which he helps a boy named Jimmy deal with the cancellation of Voyagers!
That humor like this was making it onto TV was a revelation. Here's a little bit of it from Letterman's 1985 book:
Colbert seems like the perfect inheritor of Letterman's legacy.