Wasn't there a survey done a while back with the results posted at webflyer?

My personal experience is as follows:

Soutwest: the creme de la creme, though you won't find business class or international travel on the menu.

United: excellent, rarely have a problem finding flights on 2-3 months notice, even to hawaii foreign destinations. usually there is at least one *A partner with space.

American: excellent, they have even found seats when nobody else did during busy holiday periods (at least for domestic travel).

Delta: good, but I have only booked domestic. my gf did not have any trouble booking hawaii for october (though that was several years ago -- and not exactly peak season.)

USAir: very poor for domestic seats, but they did find me a seat for Madrid in November (admittedly not peak season).

Continental: absolutely the WORST, never has seats available at Saver level and often not even at Standard level (int. or domestic). don't even bother if you are trying to book europe - it's a waste of time.