I'm using Alltel EVDO as my main connection (we're kind of in the boonies, so options are limited). It's $25/month for unlimited data tethering. If you have bluetooth on your phone and laptop you can tether them wirelessly and it's basically just like the $60+/month plan using a PCMCIA card. Only downside is you obviously can't browse and use the phone. If you take a call it'll disconnect you from the net.
Speed is pretty decent for me, I typically do 100-150KBps. Latency is HORRIBLE, though, 300-400ms typically. EVDO rev. A is supposed to be a bit better in this regard, though.
And something to keep in mind about Verizon is they are very strict about bandwidth use. If you go over ~5GB/month you'll probably get your data plan canceled. Not an issue if you plan to use it lightly, but if the connection will be used a lot for higher bandwidth stuff (audio and video streaming, downloading, etc.) this could be a problem.