Give the company a history. Is it a legacy carrier or a low-cost carrier? When was it founded? Where? What’s happened in its corporate lifetime?
If it was founded in the 1930s or 1940s, try a bunch of Scandinavian/Germanic/English surnames, as if the company was named after its dead white male founders. Johnson Air, Baker-Smith Airlines, Mason Lines, and so on. Regional names work for this era, too: Great Lakes Air, Mid-American, Schenectady and Western Airlines, Great America Lines, etc.
If it was created after deregulation it’ll have a blander, more generic name. City Connect, mentioned above, is good, as is JetAir and Clear Airways and others that have already been mentioned.
In fact, you might mention that it isn’t an airline in its own right so much as an appendage of a larger airline, like how Delta Express was a subsidiary of Delta Air Lines.
My point is that company names, like a lot of things, come and go in fashions, and grounding your company temporally will narrow the field, which is important to the creative process.
Well, if it’s for a work of fiction (or you’re willing to spend some more for the naming rights on your startup), you could check out Airlines Remembered, a nice reference book cataloging defunct airlines. (Fun fact: Greyhound once had an airline!)
Other thoughts:
AbAlto Air (Alternate: Air Morsab)
Air Phaeton
Pan Columbian Airways White Star Lines
Air Remex
Laputa Airways
Langley Layover Lines
Aero Zhuravli
Seler Aéreas
When I was a kid in the early-'70s, I had a Fly Buzzard Airlines brass belt buckle. It’s a poor image, but it’s that buzzard from the ‘Patience hell, I’m going to kill something’ cartoon. I couldn’t find another image. I’m almost certain I still have that buckle in the drawer of a box in the storage unit.
