Since you're looking for a card for general spending and general redemption, you might be best looking at a 2% cash back card:

Fidelity Rewards Amex
Household Bank Rewards Mastercard (limit of $20k spending annually)

For gas, many people use the PenFed Platinum Cash Rewards Visa for 5% back.

In parallel, you could look into some of the excellent signup bonuses to cover your travel redemptions. For example, between the citi AA Visa and Amex cards, you could accrue 150k of AA miles from $5500 in spending. See Post 2 in http://www.flyertalk.com/forum/miles...t-2-first.html