There is no question in my mind that airline service- as well as other travel services such as car rental- is indeed significantly worse than it was 20-25 years ago. ( The citation of Walmart and Sears as examples merely shows that service has declined in other areas as well !)

I think this has to do with many factors, and that ff programs play only a minor role. As air travel has become mass transportation, fares have fallen in terms of real dollars. Airlines make their money now on quantity rather than quality, and that has affected everything from size of seats to the amount of time that can be spent serving any one individual ( in line, on the phone or on the airplane).

I think, too, that decline in travel service is related to a general decline in expectation of good service. We don't really expect it any more, and so we don't get it. People have quite willingly accepted such "improvements" as thirty minutes wait on the phone while making your way through innumerable "options", which have always "recently been changed." Nobody minds if workers at the supermarket don't know where their own products are located, or if staff are rude and unhelpful. We tolerate it all because we believe it is the tradeoff for lower price. I think that pendulum will swing the other way one of these days, and there will be money to be made in providing excellent service. Maybe even in the airline industry.