Provider: I'm too lazy to find a link, but I saw a morning show segment last week where Consumer Reports had their latest cell phone provider rankings: (1) Verizon, (2) T-Mobile and Alltel, (3) AT&T and (4) Sprint.
Me, I'm a happy T-Mobile customer: I like their prices, customer service, international service and choice of phones fine. Their local coverage could be better.
Phones: No personal experience with Treos, but from looking around I sense that Treos and Blackberries are equally capable but Blackberries are just slightly smaller in general.
Hope this helps.