Go with the travelocity card with the annual fee. Each dollar spent earns you two points. At 20,000 points ($10k spend) you get a $400 credit against travelocity purchases (airfare, hotel, car rental, etc). This means you are getting about 4% back. Better than any card I know of.

The no-annual fee card earns half as much. Definately worth the annual fee if you have significant spending.