No two freshman Senators could be more different than Tom Coburn (R-Okla.) and Barack Obama (D-Ill.).

While Obama practically sailed into his seat in 2004 as the newest rising star of the Democratic Party, Coburn had to overcome opposition from party leaders in a tough home-state GOP primary and then win an equally hard-fought general election.

Their politics, particularly on social issues, are vastly different, with Obama supporting abortion rights and Coburn once advocating the death penalty for doctors who perform abortions.

And their personalities appear even more divergent, with Coburn a rough-around-the-edges, small-town doctor turned “citizen legislator,” compared with Obama’s smooth, Harvard-educated urbanity.

That’s why more than a few eyebrows were raised when Coburn and Obama jointly announced this week that they were collaborating on a bill to install a chief financial officer to oversee federal funds being spent in the aftermath of Hurricanes Katrina and Rita.

“Although Tom is considered very conservative and I’m considered slightly left of center, we both share a philosophy that whatever money is spent by the federal government should be spent well,” Obama said in an interview. “Even though we disagree on a whole host of political positions, I think he’s a very honest and sincere man.”

The two met last December during the Senate’s freshman orientation, and both credit their wives with helping to seal the friendship.

“Our wives hit it off, and we became friends,” Coburn said. “We have a good relationship, and we both have the interests of the country at heart.”

Obama said the two now regularly attend a Wednesday morning bipartisan prayer breakfast, although Obama acknowledged that Coburn’s attendance may be a bit more regular than his own. In addition, Obama will be joining Coburn in the near future as a presenter at a youth conference for college leaders. The topic will be how to incorporate one’s religious faith into public service.

On the CFO bill, Obama said the idea emerged after a conversation between the two on the Senate floor about how money appropriated for Katrina relief efforts was being spent.

“We were concerned about having some transparency and some accountability,” Obama said. “With a strong oversight process in place, at least some of the worst abuses can be avoided.”

Indeed, in a joint press release, the two noted that a Coburn-initiated investigation found at least one instance in which the government agreed to pay Carnival Cruise Lines “per evacuee, four times the amount a vacation cruise passenger would have to pay” to house primarily rescue workers in the New Orleans area on cruise ships.

“Finding out after the fact that we’re spending taxpayer money on no-bid contracts and sweetheart deals for cruise lines is no way to run a recovery effort,” the duo said in their statement.

Even though the CFO measure is taking up much of their time these days, both Senators said they intend to work together on a regular basis, particularly on efforts to make the government more fiscally disciplined.

“He’s a friend,” Coburn said. “Where we can work together, we will.”

Even so, Coburn may not necessarily be able to count on his new friend to support him in his bid to continue practicing medicine in Oklahoma. Coburn, an obstetrician, is pushing a resolution to allow him to take just enough money from patients to pay his staff and his medical insurance bills. Without the resolution, Coburn will have to close his medical office.

Obama said he has yet to make up his mind.

“I’d love to give Tom the benefit of the doubt,” Obama said. “I think he wants to continue practicing for the best reasons. My concern would be what kind of precedent it sets.”