I think there are some credit card practices that could be framed as fraud (You can change my interest rate without telling me? And without telling me you won't tell me? Seriously? What the hell?) so the government would have to be involved even in a strict libertarian society, but I never like where this is going.

Libertarianism, as a political concept was an idea invented by David Nolan to suit his political theories. He had a chart, and a quarter of it is various types of libertarians.

If you like more social liberties than the American center, and more economic liberties, and are willing to forgo some amount (even a small amount) of government services and protections to achieve them, then you are some where on that quarter of the map. You don't necessarily have to be way off in the corner with the anarchists or defend every idea they have.

That seems clearly within the scope of legitimate concerns of government, given that air travel is already heavily regulated

This argument doesn't work. Just because you already have heavy regulation, doesn't justify having more regulation. Also, many libertarians would say that the solution should be to simply remove much of the heavy regulation of air travel.