This is all IMO, so no flames please. Just my $0.02
Nextel doesn't make cell phones. They use Motorola phones and infrastructure. The quality is ok, coverage is average, the menu's are poor.
AT&T has excellent coverage/networks.
Nokia phones have excellent menu's are small and look cool.
Motorola Timeports are kludgy (I hate flip phones) and have crappy menu system.
That said, I'd still buy a Motorola phone every time because their RF performance is better than Nokia. I can learn my way around a crappy menu but I don't like (and can't learn my way around) poor reception.
Sprint is crap.
I currently use Verizon, but will probably switch to AT&T in the near future.
I have yet to look into Voicestream, but if they get GPRS working right I might get one.