Ask HSBC for a cc, since they approved your car loan I wouldn't think you'd have a problem. Plus they sent me many many offers for credit cards in the months after my discharge. I would try to wait 90 days and you may well get a no annual fee offer. Or you can ask them and tell them you need a no AF card or no deal.
There is also Capital One and Juniper who tend to offer cards to recently discharged individuals, so try both of these. But try to hold out for the no annual fee cards, so you can build history and not be tempted to close the cards out once you become a prime borrower again and the Chases, Bank of Americas and even AMEXs come calling.
