I would rather have a zero credit score and $1mm in the bank than an 850 credit score and no money in the bank. Consumer debt does not help you build wealth. I dont worry about credit score when paying off debt.
That seems like a mixed message; having an 850 credit score and $1mm in the bank aren't mutually exclusive. Worrying about your credit score while paying off debt is nonsensical as once you prove you aren't a consumer sucka, your FICO score positively reflects your ability to manage (read stay out of) debt. Similar to what Svonyk has proposed, keep your cards open as they will extend your average credit history which is a huge component in determining your FICO score.
Regarding payoff strategies, the math says to pay off your highest interest card first then snowball that payment amount into the next highest interest card, rinse and repeat until no more cc debt. However you could also pay off the lowest balance first and snowball that payment amount into the next highest balance etc. to receive the psychological boost of making a dent in your debt.