I agree with sami - it's generally important to keep new players (the guy who runs this game should definitely know that, after all!). The challenge is that the way in which new players are "protected" has to be natural in some way. You need some mechanism that ensures they have a fighting chance, but it also has to be realistic and make sense within the context of the game worlds. I propose the following options:
New airlines should start with a higher company image Usually, a new airline in the real world will generate some "buzz" in that it will attract people who are tired of the older, more established airlines. A starting company image of 10, with the first few routes starting at a route image of say, 20, would give new players a faster start. It's also a completely rational and realistic concept - New airlines almost always end up in the news!
Initial aircraft purchase Capital is a huge problem for new airlines. Usually, you end up being stuck with tiny old aircraft, or you end up having to lease aircraft, often from your own competitors! This makes no sense. In the real world, new airlines usually have at least a decent investor backing. Upon founding, a new airline should be given some sort of allowance to directly purchase 1-2 medium aircraft. This doesn't mean having airlines start with $30 million or anything. It could be similar to the existing mechanic where aircraft are used as loan securities, only without the actual loan in place. Essentially, your airline would be "held hostage" by investor demands that you maintain assets early on!
Help out the smaller Base airports! In previous game worlds (different account - I accidentally allowed my old account to lapse), I've had a lot of success coming in late by sticking with smaller airports for hubs. My favored airport has been Raleigh-Durham International, though I'm currently running a KABQ airline in GW#1 that looks like it has pretty good prospects. The problem is that I'm probably not going to be able to expand far beyond 20-25 aircraft before running out of profitable routes. Granted, I'm sort of banking on building up a CRJ-700 fleet later on in the 1990's so I can hit some east coast destinations. But after that...I don't really have anywhere to go. An option already discussed was tax incentives - maybe encourage basing while discouraging secondary hubs (tax break for airlines based there, for example).
In general, my big point is this: Realistic, "flavorful" (in the sense that players can understand and "get" them) mechanics will work. Arbitrary rules will not. Look at the recent thread on slot trading - there are natural ways to effectively manage the landing slots, but just making rules that lack context will just lead to people finding ways to work around them, or worse, people will find ways to use said rules for abusive personal gains.