I would recommend Virgin Mobile
https://www.virginmobileusa.com/ . I switched to them from ATT (I was also paying about $70 a month) and I now pay $35 a month for 200 anytime, 500 evenings and weekend (starting at 7) minutes, 1000 text messages, and 20 MB of data.
I've had very positive experiences with the customer service and I they were able to port my ATT number in about 30 minutes.
Virgin runs on the Sprint network, and I get good use out of my 3g Shuttle. It's sufficient phone, but not amazing - and that seems to be the consensus for all of their phones. I keep looking for a better deal, but have been unable to find anything that is even close to competitive with this. I've been happy with them for the past 8 months, but I don't have a contract with them so I could drop them at anytime.