A commenter at the TiVo Community Forum nails the difference between The Tonight Show and The Late Show:

Letterman's show is not a Talk Show .... it's a *SATIRE* of a Talk Show. It's just a big giant goof on the whole talk show genre. That's why they have Stupid Pet Tricks and Larry Bud Melman and Mujibur and Sulaiman and Does It Float and canned hams for prizes, and indeed even why Letterman's interviews are so un-interviewy. All that was initially designed to make fun of how talk shows had always done things before.

Paul's role is to be the satirical Talk Show Band Leader. His role is NOT to be a professional band leader on a talk show .... his role is to MAKE FUN of (i.e., spoof) professional band leaders on talk shows. So, e.g., the "cheesy" songs, the intermingled laughter, his look, etc. all satirize what a professional band leader (like whoever the latest lackey on Leno is or Doc Severinsen) would do - that's why the songs are so one-dimensional and corny.

On the other hand, Leno's show plays it straight - it's not a satire of a talk show at all ... it's an actual talk show.

It's not surprising that the two camps (Letterman supporters and Leno supporters) are so diametrically opposed. Letterman supporters can't stand what they perceive as the staleness of the talk show genre and love watching it be goofed on. Leno supporters on the other hand still like the traditional talk show format, and don't "get the joke" that Letterman is playing on it.

See, now it all makes sense!