Airlines in the US are a clear example of how a deregulated "free" market can serve customers badly.

There is no such thing as "the" free market. Every market has rules, and a free market simply means one in which everyone is allowed to play by the same rules. Changing the rules can make a big difference between one free market and another free market.