Assuming the Internet Sharing program is still there somewhere (Start, Settings, Connections tab - OR - Start, Programs), you may be able to unlock it from the registry by going to HKEY_LOCAL_MACHINE/Comm/InternetSharing/Settings. Find the value ForceCellConnection and set its data to blank (remove the connection name listed there). The next time you launch Internet Sharing you should see 2 drop down lists. Select USB or Bluetooth PAN, depending on how you want to connect to your computer. Select the appropriate VZW data connection from the second drop down list and press the Connect softkey.
wmwifirouter is awesome. You can also do a web search for ICS.CAB (Internet Connection Sharing) and install it on the device easily enough. It seems Verizon likes to strip that CAB out of WM to try and get the extra $15/month.