That was just a warm-up for the main event, however.
Letterman's headliner was Hillary Clinton, who walked onto the "Late Show" stage to the strains of Bruce Springsteen's "Born to Run," ribbed Letterman for his many jokes about her pantsuits (while wearing one, of course), and answered some serious questions before delivering a Top Ten list of comedic campaign promises.
Most popular with the "Late Show" audience were a promise to allow taxpayers to roll dice for double or nothing against the IRS; a pledge to loan out Air Force One to folks who have trouble getting a flight; and a promise that her vice president "will never shoot anybody in the face."
Letterman took Clinton back to her first job after graduating from college, as a fish gutter in Alaska.
"The job was to be in hip boots with an apron, with a spoon," Clinton recalled. "The salmon would be brought in, they'd be slit open, and the caviar would be taken out and then they'd be thrown in a big pile. My job was to grab - I mean, these are big fish - to take a spoon and clean out the insides. That's called 'sliming fish.' "
It was, Clinton said satirically, "the best preparation for being in Washington that you can possibly imagine."
Asked about the tens of millions she's already raised for her campaign, and the many millions more that are likely to be spent, Clinton said she'd like to see a switch to "public financing, where people don't have to raise money like this."
"There's a great public financing system here in New York City, and I think it's a terrific model," she continued. "But, again, under our constitution, the Supreme Court has decided that your contributions is a form of political speech... So it would be very hard to come up with a system that would really work. But I'm gonna do everything I can - now, as a senator - I hope, as a president - to try to deal with it."
As for the campaign itself, the New York Democrat says it's long, intense, and takes stamina - which she has.
"I find it exhilarating," said Clinton. "I get to travel, go in and out of people's lives in a way that few folks ever get to do. You're in people's homes, workplaces - everything that you can imagine that's important, and they're telling you about it."
The campaign trail, she acknowledged, is also "incredibly draining... it seems to be what our system demands. Maybe because it's the hardest job in the world, they want to make the candidates go through very tough preliminaries."
The challenges are already in place, said Clinton, for the next president.
"I think it's going to be especially hard following President Bush and Vice President Cheney; I think there are going to be a lot of problems that we'll inherit," she said. "I wouldn't be doing this if I didn't think, number one, that I could win, and number two, that I could do the job that the country needs."
"I think the fact that I would be the first woman president is a good barrier for America to break," she continued, pointing to female leaders past and present, including Margaret Thatcher, Indira Ghandi, Golda Meyer, and Angela Merkel. "We're the land where we say to everybody, 'Live up to your potential, live your dreams,' right?"
"It certainly seems overdue," Letterman said about the prospect of a female president.
"I find it so exciting as I travel around the country, a lot of people bring their children, particularly their daughters, to meet me. And that's very touching," said Clinton. "I cannot tell you how many women in their 90s come out to see me. And they all say something along the lines of 'You know, I was born before women could vote and I want to live long enough to see women as our president.'"
Being the person who might do that is a big responsibility, said Clinton, stressing that her qualifications to do the job - and not her gender - are at the heart of her campaign.
Letterman asked what it's like campaigning with a former president. Does Bill Clinton ever slip and forget that he's not the candidate?
"If the constitution had not been amended to make it two terms, he might be running," said the former First Lady. "He's been extremely supportive. But he loves being out there with people, and hearing the stories, as I do. He gets into it and gets excited about it. It's fun! You should come with us some time."
Zeroing in Iraq, Letterman asked Clinton whether she believes there will be a permanent U.S. military presence in Iraq.
"I hope not. That sure is not what I believe we should do," said Clinton. "There are no good options. That's one of the problems we have to just accept. But I think we need to begin to withdraw our troops now - bring them home, make it clear they're not going to continue to referee a civil war."
"We've got to put much more pressure on the Iraqi government, which has not lived up to its responsibilities. There is no military solution, and the political side of the equation has been neglected by the government in Iraq and, to some extent, by our government here," she added. "And then we've got to have intensive regional and international diplomacy."
"We will have some continuing problems that we're going to have to deal with. We've got to withdraw our troops carefully and safely," said Clinton. "We have a lot of Americans who are not in the military who are in Iraq: they are contractors, civilian employees. We have a lot of Iraqis who sided with us: they were our translators, our drivers, they did other jobs - I don't want to leave them to be at risk of perhaps assassination, kidnapping, whatever."
"We've got to continue to try to deter and detain al Qaeda - which wasn't there before, but it's there now. And I think we have to help the Kurds, because they've behaved well in this - they've tried to do the best they could, under the circumstances."
"What do we then say to people in the military," asked Letterman, "who might ask 'Gee, what was this all about, then?'"
"I think we say to them that they performed heroically, and they did everything they were asked to do. It's important that every American understand that," said Clinton. "They were asked to rid of Saddam Hussein and bring him to justice, and they did. They were asked to give the Iraqis free and fair elections to chart their own future, and they made that happen. They were asked to give the Iraqi government the space and the time to make these political decisions that only they can make, and they did that as well."
"We should be very proud of the way that our young men and women in uniform performed, and we should make it absolutely clear we're going to take care of them when they come home. If they have health care needs and other needs, we're going to take care of them as long as it takes," said Clinton, noting that there are some 30,000 wounded, some of whom are dealing with brain injuries.
By Francie Grace