Verizon or AT&T
My company has tried AT&T, Sprint and now Verizon in the last 3 years.
AT&T were (and still are) the most expensive, Sprint was great, WHEN it works, and also VERY expensive out of network. We changed to Verizon with Motorola (free) phones just last year.
I still carry my personal AT&T with a "One Rate" no roaming charge plan with a Nokia AND carry the Verizon phone (don't you hate that - all I need is a pager too!). Both work equally as well, though I prefer the Nokia for ease of use and quality. I'd be hard pressed to choose on quality of service between AT&T and Verizon, but the plans at Verizon are "friendlier."
I've flown with a Gulfstream guy who had Cingular. He used my AT&T phone to call his wife almost every day on the road. It's probably changed, but it's worth checking into. Roll over those minutes, right?
Alltel? Haven't heard much, sorry, can't help.
Be careful about the contract length, a year is fine, 2 years, and they better be giving you something.
Hope this helps. Call me after 9:00pm or weekends, it's free for me!