I have a droid and I can answer most of your questions about how they handle android. For the most part they leave it alone.
They do not push any ads or recommended apps to you. I found out about NFL mobile on this site and that is the only way I knew it was available for my Droid.
Google maps navigation is on Android 2.0+ and yes you can use it for free, I don't even know if you can use Verizon Navigator on an Android phone even if you wanted.
The Android market is full of apps to customize your phone with ringtones, make your own ringtones, notifications, etc. Verizon does not interfere.
They are slow on software updates. It took way longer than it needed to for the Droid to get Android 2.1, who knows what the delay was. My wife's Eris still has not got an update from 1.5 or 1.6 or whatever it came with. It is running 2.1 thanks to the info on this forum, but my daughter has one too that I didn't update and there is nothing from verizon.
BTW, Incredible is a great choice, I'm getting mine in a couple weeks!