Could they have offered to pay the tax? Or would that then trigger more tax, creating some kind of infinite loop of gifts and taxes?

Offering to pay the tax does trigger more tax; but as the added tax is less than what you add to the price, the total amount converges (as long as the tax rate is less than 100%). To have the recipient end up with a net payment N after taxes you've to pay N/(1-r), with r being the tax rate.

With a 25% tax rate and car value of $28,500; to make it a tax-free gift Oprah should've paid an additional $9,500.

Yeah, the term is "grossing up" and it's often done for bonuses and things. I've also seen it on sweepstakes. One for Fage yogurt offered a dream vacation to Greece and included a gross-up to pay the income tax.

Yes.

There’s a great YouTube view about exactly this by Stand Up Maths if you want to go down a rabbit hole.

https://youtube.com/watch?v=3cNdM7W0VlQ

To be fair, $6000 for a brand new car ain't so bad, even if it was a Pontiac.

The problem was that the people in the audience all needed cars and couldn't afford them. They didn't have money. Finding $6000 to keep a gift when you're broke is a hard problem.

IRS does offer payment plans at least for some types of tax debt. But really, if you need a car but are unable to get $6000 to obtain one, I'm not sure if you have that much better luck in the used car market, since a car would still require some thousands that you either need to have at hand, or get a loan to. If you can't get a loan for a $6000 new car, can you get a loan for a $3000 used car?