Definetly don't go Incredible. Wait for X, or possibly EVO4G with Sprint.
That really sucks that VZW is charging to use tethering, a feature that's native to the phone/OS. I'm hoping that 3rd party solutions, like we have now, will allow tethering without going through VZW. Then again, I haven't had much need for tethering yet.