Another vote for coverage. You need to pick the one that has the best coverage where you will use it - where you live, work, travel and play. All carriers have holes in coverage. None are perfect. Do your homework first.
As for speed, Verizon devices generally connect on EVDO which is faster than EDGE. You will not notice the difference when it comes to email, maybe a minimal difference in Internet surfing, but a lot of difference if you tether.