Its doubtful that Verizon would ever be cheapest.

First of all, it depends on the speed you want. Verizon and Sprint are fastest with EVDO, ATT has EDGE which is the next fastest, and then there's T-mobile which is the slowest (also EDGE, but I heard its slower than ATT's.)

Sprint has much cheaper prices for data than Verizon. Technically, you need a specific tethering plan for Sprint to use the phone as a modem, but with certain phones there are ways around it. I'd say sign up for a Sprint Employee referral plan (there are email addresses for it all over the internet, just search), get a Centro for $99, apply the tethering hack, or if you can't get that to work, try PDAnet. (See the Treocentral forums for these.) The SERO plan gives you 500 anytime minutes, nights and weekends at 7pm, and unlimited data and texting, all for just $30 a month.

This is a slightly gray area, but as long as you're not doing Bittorrent downloads or downloading gigabytes a month, then you should be fine.