Ordering from Cingular has been a nightmare. I have to wait a week for a phone and they did not even have the courtesy to inform me. Verizon phones suck, but they're (the service) at least mostly on point.
My Motorola e815 is fantastic! Great battery life and the best reception on a phone. I couldn't be happier with Verizon.
Verizon neglects the handset business. They get a bit lazy - always relying on coverage... . All that really matters is how your chosen provider works where you live and work. Don't worry too much about the "phone".