VA and FHA loans are all the same rate. They are not credit based. They just need to make sure you can make the payments.
Now that you have located some lenders, what I did next was to interview them. One of the most important things (to me) I made sure to ask was their origination fee. Some places quoted me 1% of the loan amt. Some offer less such as .5%. Remember that origination fees are negotiable.
I was able to talk my lender down to a .75% origination fee even though they don't offer discounts but given that they knew I was serious and had my info, the ball was on my court. By the .25% off of the 1% origination fee, I was able to save about $1000. Not too shabby.