The Pixies play “Trompe Le Monde” on David Letterman in 1992, backed by Paul Shaffer and the house band. Is it appalling that I like the addition of the Paul Shaffer ELO-style keyboard solo to this song?
Also, did you know that Paul Shaffer co-wrote “It’s Raining Men”?
Quomodocumque 
Yeah, this clip makes me shudder. I think it was their TV debut too (but I could be wrong and as usual didn’t check). I did not know that tidbit about “It’s Raining Men”
No! They were on David Sanborn’s show “Night Music” in 1989 playing “Monkey Gone to Heaven” and “Tame.” It blew my little college mind. Hey, like everything else ever filmed, it’s on YouTube:
Letterman was careful to say “first network TV appearance” — I think “Night Music” was syndicated at the time, having been dropped by NBC.
Also, I read in Ben Sisario’s book about Doolittle that Jay Leno asked the Pixies to come on around the same time and play “Here Comes Your Man,” but they said “We play “Tame” or we don’t play,” and, well, that’s the story.
I didn’t even know David Sanborn had a TV show. I will have to check out this clip! Now that you mention it, Dave says “first network TV appearance” frequently. I will now appreciate the distinction.