I, too, recommend the Starwood Amex, but also make sure you get a Visa/Mastercard. Why? Because Amex isn't accepted everywhere and you want to get miles for every dollar charged.

Which Visa to choose? I'd take the affinity card associated with the airline you fly most. Also make sure that airline flies where you want to take your free trip. For example, don't take the US Airways card if you only want to go to Hawaii.