I recommend taking a good look at America West. It has one of the most flexible elite programs around: if you get comped even to their lowest level -- Silver -- you will almost never fly coach again. And they will comp you -- fax them your last Delta statement and they'll give you immediate Silver, plus a chance for Gold after a few flights.

In addition to unlimited upgrades -- and flights to many if not all destinations you mention, it offers:

1) 3000 mile bonus for web-booking a round trip -- highest in the industry. Scheduled to end in Jan, but they may extend it.

2) Low fares, no Sat nite stay requirements. Even last minute business fares are cheap

3) 2nd best on-time performance of any airline.

4) Very friendly, flexible personnel. No snooty United-style attitude.

The airline has its detractors, but for the most part their complaints are out of date. I fly HP routinely out of SNA, always get F, and have no complaints.