Go to Naval Federal Credit Union and look into joining. You must have a relative or your wife must have a relative that is/was in the service. They are *very* liberal with that. Start off with putting some money into a savings account. Get a secured card. If ready cash is an issue perhaps getting another card of any kind is not a good idea until things get a little better. After several months of exemplary payments, the secured card may "graduate" into an unsecured card. Meanwhile, the customer service people are terrific and generally knowledgable. You want to focus on building a relationship with them - they're old-fashioned that way.
At least you have good credit scores. But, you're like a fast boat in shallow water. You feel the wind in your face, but your potential creditors see the bottom, and it's a little too close for their comfort. Stop with the apps, so those will clear out. Be patient. Read the stories here for encouragement and enlightenment. Good luck!