Definitely follow BBS's advice on utilization. If it's a little high right now, get your Navy card to report a lower balance and apply next month. And as BBS says, the age of your Navy card is important. Some lenders, notably Chase and Citi like to see some age and probably thicker files.
Working with the information we have, I'd avoid cards that have high minimum credit limits. As examples, the Captial One Venture and the Chase Sapphire Preferred have $5,000 minimum limits. With a $31,000 income, you should eventually be able to obtain cards with limits in the $5,000-plus range. But for now, your "experience" with only a $2,000 limit would likely hold you back.
Cards you might want to take a look at include the Capital One Quicksilver, Capital One Premier Dining Rewards, and Bank of America Cash Rewards. People tend to be able to get them with fairly thin files. Discover might be a possibility too, although I'd feel better if I had a second card with a bit of history before applying with them.
