No credit card required
Browse credit cards from a variety of issuers to see if there's a better card for you.
if you have 16k to pay off your debt do so. this will raise your scores. then pay the remaining 4k balance asap until paid off.
negotiating lower payments is only a consideration if you don't have the money to pay and if noted on your cr, as is typical, can negatively impact scores.
I agree witht he above. Do not settle. Even if it does not have a huge impact on your scores, it will have an impact on your ability to get credit with these people later. Also, settelement is like the step before BK. If you have 16K in cash and are still on time to all of these accounts, it sounds like you may just need to hold down some spending habits (or you had some serious problem in the past and used credit to get throguh it) My point being that is sounds like you should be easily able to pay off the 16K that has the highest interest rate, and then use the payments you have been making on the 20K towards the 4 K and get it all PIF in the next few months. Then, the accounts will remain open and you will have a big positive impact on your scores due to low utilitization.
The flip side is that if you settle, the accounts will all be closed and it will be difficult to get credit for quite awhile after. On top of that, your utilization and credit history length will be hurt as well. You could see a pretty big drop in scores between the settlements, the history, and the util.