No credit card required
Browse credit cards from a variety of issuers to see if there's a better card for you.
score wise you would have been a little better off letting a small balance report on one card instead of paying them all in full. still though you should see a pretty significent increase going from 80% to 0% utilization which will obviously help with your approval.
Don't ask why. It's just how FICO behaves; no rational reason we can come up with.
You don't have to pay interest though. Just buy something for more than $1 on one card every month, let it report on your statement, pay it off. Should be interest free use of a credit card as long as you pay off the statement in full.