Take a look at the United program.

They have a lot of flights out of IAD, and they fly to Europe, Asia, and South America. Additionally, they have an extensive partner network which will take you almost anywhere in the world that you would ever want to go. You don't have to fly much at all (only 25,000 miles) to get Premier status and that will get you Economy Plus and a little more leg room . If you fly more, you will figure out how to keep yourself in first class.

If you have to travel to a lot of podunk towns, HHonors is probably the best program, because there is almost always a Hampton Inn in every town of any size in America. Hampton Inn stays are pretty predictable and count toward status just like a night at the Waldorf Astoria.

Good luck in your job!

If you want to fly to Asia and Europe using frequent flyer miles/credits, JetBlue and Southwest are worthless programs.

If you'll be on United's/USAirways's routes mostly, look into a Star Alliance program since that'll get you your award redemption options. (I use United, USAir, BMI, ANA and SAS's programs for my Star Alliance flights.)

If you'll be on American Airlines' and Alaska Airlines' routes, then AA's program is a great one.

For you to get the best advice, a lot more things would need to be known (e.g., anticipated flying patterns, anticipated lodging habits, purchase habits, redemption desires, etc.).

I think you've gotten some good suggestions from previous posters.

Welcome to FT. Enjoy.

The LCCs tend to have better economy class than the legacies do for non-premium economy for non-elites. I'd rather fly Southwest than standard economy as a non-elite on United for a short notice business trip, since a short notice booking on United usually means getting an undesirable seat if you are not elite. Plus, Southwest has a bit more legroom than United's standard economy.

Which brings up the question for the original poster: how much is "a lot" of flying? Specifically, compare the expected amount of flying to the elite qualification levels and elite perks of various airlines and take that into consideration (as well as which airlines fly where you want to go) when choosing FF programs. Elite perks (like using the empty first class checkin desk or United's Economy Plus seats with more legroom) can make a significant difference in how pleasant a legacy airline flight is.

If your flights are heavy with Alaska Airlines' routes, the Alaska Airlines program is probably better than the American Airlines program, since Alaska can also collect mileage from Delta, Continental, and Northwest flights (as well as American), and has a lower domestic economy award ticket threshhold.

Since you'll be flying from mostly Dulles, I agree with the previous posts that say UA is a good choice of FFP to follow.

Since you are obviously a newbie at this, it is worth mentioning to you that one of the principle advantages of these alliances is that you can fly on any airline in the alliance, and credit your FF miles to some other airline in the alliance.

So, in your case, if you concentrate on the United MileagePlus FF program, you can also take flights on US Air (another Star Alliance member), and use your United FF #, and credit that mileage to your United Account. That way, you get all the miles in one place, getting to elite status faster, and getting to award levels faster.

(This assumes, of course, that US Air continues to be part of the StarAlliance, if there is a Delta merger. Who knows.)

Then, for redemptions, you can look for award seats on United, US Air, and the other Star Alliance member airlines to Asia and Europe.

...and America West!

Also you get elite qualification miles to United when you fly USAir or America West (and other international carriers).

Try to focus your miles on United so you can get Premier status and Economy Plus access. Out of Dulles, United is the no-brainer choice.

I go to Baltimore from Seattle and drive to Dulles to get the best non-stop options to Seattle. With United you can get many non-stops to SEA, SFO, LAX, PDX on the west coast, and redeyes back if you need em.