I'm with Verizon and I've found them to be great as far as service goes, but they really lock down the phones--can't add free ringtones/wallpapers/whatever. They charge for everything.
Reliability is great, though.
Had AT&T/Cingular before Verizon and they were absolute shit.
edit: I'd use Amazon.com or letstalk.com to sign up/purchase a phone. They usually have some hot rebate deals going on. I got my last phone for -$150.