You'll recover, no doubt about it.
I don't know when CapOne reports. Maybe others could comment. But usually CCs report on the day your statement cuts. Ideally, you need to be happy with your balance on the statment date.
Store cards...I have Macys, Bloomies, and Target, and I like all three. I only used them twice in the last 6 months, but they seem good. Others may include Wal-Mart, Best Buy, Circuit City, Gap, Old Navy, etc. The favorite here seems to be Target.
Before applying, though, try to repair your credit. Advice is great in these forums. This will cause your scores to rise and improve odds during applying.
Per your DH, its up to you if you want to pull those too. It does get expensive. Personally, pulling before repair gives you a map or guide from which to work from. You could always work off the free copies from annualcreditreport.com so you can see what is good and what is bad. Don't pay for those scores because they are not FICO scores.
And having side jobs is good. I did the same as you did. Prepared 1040s for folks using TurboTax (if they only knew). Also did corp returns 1120s, 940s, 941s, etc. Great for cash this time of year!
Some here may cringe when I mention this, but I recently started to listen to Dave Ramsey on-line, but his radio show is most everywhere. Dave is anti-credit. On principle I agree with him, but in the short term, having good credit is important for a great lower mortgage rate if you can't pay in cash for that home. But he has some excellent pointers on getting out of debt and saving money.