My comments:

1) All major US airlines have the 500 mile minimum for a flight, that's not an issue in where you'll switch.

2) All major US airlines have a credit card partner, that's not much of an issue except in as much as one card is superior to others in some cases. (i.e., you can earn base miles on the Platinum DL AMEX card if you charge $25k + per year).

Your primary concern seems to be upgrading internationally on decent priced tickets. To do that, you've got a few options.

1) AA ~ You can upgrade all published fares internationally with miles. If you get Executive Platinum (100k miles/year) you'll also get 8 (I think that's the right number) VIPOW's that allow you to upgrade a trip one way (up to three segments I think) on any published fare. This is probably the best program for international upgrades. The downside is you only get 4 500-mile upgrades every 10k miles flown, much less than unlimited obviously.

2) UA ~ If you can get to 1k (100k miles/year), you'll get 6 SWU's each year good on any non E-fare one-way internationally. (Note: there has been a lot of trouble with the new ones concerning "internet" fares being excluded, but that seems to be getting fixed and now appears to only mean Efares). For mileage upgrades though, you're limited to higher fares like on NW, so if you don't make 1K or take more than 3 R/T's internationally per year, you're out of luck. Same problem with UA as on AA on domestic upgrades also, much more limited.

I think those two are your best bets, and I'd go with AA over UA personally ... but it depends on their service to the airports you mentioned, which I am really not familar with.