AA and UA should be slam-dunks!

AA Mastercard: 10000 bonus miles, no fee for 6 months, and add in a little iDine to get to 25k. (There is also a 12500 bonus mile offer if he needs a FAST award, but he pays the annual fee up front on that one.) Unless he is a high-volume CC user, dump the AA card before the six months is up.

UA Visa: 20k bonus -> brings your buddy up to 36k faster than you can say HAWAII!

US Airways and NWA: given that he is not a big traveler and probably doesn't want a walletful of airline credit cards, maybe wait on these. Get him to free ticket level on UA and AA first. If he is getting hooked, have him dump the UA and AA cards and grab US Airways and NWA credit cards and add a little iDine to get to those award levels.

If he is geeked about Hawaii, there is plenty of easy partner activity to take him up to 35k on AA and he has two free tickets. (Granted they on different airlines, but this might end up being a blessing when he's searching for availability.)