Their Android devices haven't been horribly locked down. Pretty much all HTC devices can be rooted trivially, and the Motorola lockdown is a charge being led by Motorola.

Verizon is surprisingly hands-off. I still wouldn't go with them by virtue of being forced into a contract just to get a handset, maybe that'll change when LTE comes to the fore.