Love how this thread goes instantly from "BB/Android would be overkill" to "Tegra 2 or bust!"
The question is really how interested and willing you are to customize your own experience with hacking, mods, etc. Not at all: wait for WinPh7 or iPhone (neither are on Verizon yet). A lot: definitely Android. (The Droid 2 and X are pretty solid out of the box, though... The Samsung Fascinate -- $1 at BB BF -- is the best current Verizon if you're willing to play with it.)
Oh yeah, don't be sure you need a physical keyboard until you play around with Swype. IMO it's sufficient reason to go Android.
As far as upgrades, I think Verizon allows them one year in at a somewhat higher price ($80-$100 more?). But the phone you choose now won't affect the upgrade process later.
You realize basically every single smartphone can be hacked for free tethering... For some it doesn't even require root access.