I had Verizon for about eighteen months. I had this Samsung that looked cool, but was ancient. The hinge was prone to snapping off, which mine of course did, and the people at the store were great and empathetic but wouldn't even give me a refurbished phone.
I looked at the Chocolate and the Sidekick 3 while I used our family's spare Sprint phone, and I decided that Verizon didn't work for me because it didn't work internationally, was expensive (because I don't know a lot of people on Verizon), and had mediocre and overpriced phones, so I went with the Sidekick. (though my local T-Mobile tower is under repair, so I switched to an iPhone on att.)
This is just my experience. I feel that your money doesn't buy you a good phone with them, and if you want a reasonably good phone, prepare to pony up. The international was a big thing for me. Customer care is not bad, but not good. I really wished that they had given me a refurbished phone instead of having me choose between an ultra cheapie clunker and a $270 Chocolate. Also, I now know a lot more people on at&t, and our family's paying about half of what we used to pay to the other three.