Agree with most of what has been said, with a few additional thoughts:

Car Rental: Hertz and Avis are the best, Hertz definitely has the best service. Hertz also runs frequent bonus promos with WN (Southwest Airlines). The current (recurring) promo offers 2 credits for every car rental thru mid-December. At that rate you'll have a free ticket on WN for every 8 rentals. IMO, a much better deal than a few measely air or hotel points.

Credit Cards:

With a self-described credit score in the "600s" I would not apply for more than 1 card every six months. That score is okay but not great, and opening too many card accounts will tank the score and likely render you ineligible for the cards you want. Many of the best mileage/points cards require minimum scores of 700-720, so you are already pushing the limit on approval. Make sure your first card is an MC or VI as Amex is not accepted everywhere. Citi AA is a good choice for your situation, but if you have significant foreign travel you should also consider a Capital One No Hassle card which provides a cashback rebate and more importantly, no absurd forex conversion fees. CapOne also has a lower FICO score requirement, which may work to your benefit. You should also consider a Chase or Citi card that provides 5% cash back on gas purchases. Again, IMO the 5% cash is worth more than the miles for as long as it lasts (currently a year). I just got a check from Citi for $215 for 6 months of gas. I like it when the bank pays me.