Alltel is a very poor choice. I think they have one of the worst plans around. I have 2 phones with Sprint and am happy with them. The rates are good and the minutes included work well for me. They've sort of changed in the past couple of months, but overall, still a solid company. The only downside is that you have to buy the phone, while with some of the other companies it's a lot cheaper (or free) as long as you sign up for a year. Be sure to check the PCS store and online to see the promotions. I ordered online b/c I got $50 off the phone. I opted for Sprint b/c at the time, I did not want a year contract, but I eventually signed up for it in the end.
I use my cell for all long distance calling. I have the $34.99 (1200 min) package and have NEVER used all of my minutes. You can also switch you LD carrier to Sprint and get $50 plus the montly fee waived, which is a nice deal, too.
From the commercials I've seen, Verizon looks ok, too, but I know little about them.