If you have decent income, you should join PenFed and apply for their Platinum Cash Back Visa, it's one of the best in the business. When it's time for you to buy a car, they'll give you an excellent rate.
PenFed seems to be exactly what you are looking for. As long as you have good income (they will ask for personal income and they will ask for paystubs) they will probably approve you.
PenFed Platinum Rewards Visa is one of the best cashback cards for gas - 5% cashback which you receive as statement credit each month.
Plus you get 2% cashback for supermarkets and 1.25% for any other purchase. They also currently have a temporary 5% cashback on airfare.
They have great auto loan rates - currently as low as 3.99%.
In your situation, there's a whole bunch of great cards that you could get approved for. (edited)
For example, a not so well known card that has 5x on gas and other auto perks is the Chase AAA of Northern California Nevada and Utah (of course, if you reside in those states).
Do I have to join the National Military Family Association just to apply for the Pen Fed card? I don't want to pay the yearly fee for it only to be declined for the card.