Treo Tethering on Verizon
Unlike Sprint, I do not believe there is a plan on Verizon. I use PDA Net from June Fabrics, if you go to some tothe Treo Sites (treonauts, mytreo.net) you can find the writeups and reviews of this and other.
PDA Net advantage is that it is a 1 time cost of about 25 bucks and you can get 2.5mbps in EVDO areas.