Depends on your provider but most companies use G.711 or G.729 (64kbs and 8kbs respectively) for their VoIP clients, so you should be ok with any 3G connection or higher. The problem arises when your latency to the servers start to exceed 150-200ms or so, then you'll start to suffer from QoS issues.
FWIW, Vonage's Low, Med, and High audio quality settings require 30kb/s, 60kb/s and 90kb/s respectively.
Rather than tethering, another option may be to setup your VoIP account on the Incredible itself via a SIP client such as sipdroid.