No credit card required
Browse credit cards from a variety of issuers to see if there's a better card for you.
Reducing the balance on the auto loan will do nothing at this time. Having 1 revolving account is okay, I would see if you can get another (store card, etc). If it was me, 1 installment loan and 2 revolving cards will do you good ... sit on them for 8-12 months and continue to pay on time.
Your biggest obstacle are the paid collections/public records showing up. You should start the GW process and see if you can get them removed.
It's when you send (mail, fax, email, etc) Goodwill letters to the company reporting the negative tradeline. You send them letters asking if they could delete the negative marks off your credit report.
You can find a heap of information on this site ... under the "REBUILDING YOUR CREDIT" tab.