Request higher limits on your exisiting cards. Except maybe the Firestone card. This is better for your score than opening a new card in the short term.

Then, to be frank, you need to make and stick to a budget. Eliminate credit card debt and only put purchases on a card that you can pay off each month and then the APR won't matter.