Congrats :-) I'm extremely jealous.
You can use it with wifi (including installing apps and so forth), but obviously that'd only be available in a few restricted locations. Things like Google Navigation would need a 3G connection to be useful, since you'd normally be away from home when using them.
Which version of the operating system is currently on it? If it's 1.6, then you can upgrade to 2.2 in order to get Flash, which will allow more videos to be played.
Firstly, is it a locked or an unlocked unit? If it's locked, then only one particular network can be used. If it's unlocked, then any network USING THE 3G FREQUENCIES AVAILABLE ON THE HANDSET can be used.
In most of the world, the 3G frequencies are reasonably standardised, so phones can be used on any network, but in the USA I gather that it's all a bit chaotic, and I don't know whether or not Verizon would be OK.
Are you tied onto Verizon (i.e., have a long contract to run?). If not, you could always port your existing number onto a different network.