Does Google Maps Navigation for Mobile work on Verizon Android phones
It doesn't apply to Google Maps Navigation AFAIK but you should ask this specific question to your local Verizon dealer. 

For instance, I use Google Maps Navigation on my HTC Droid Incredible and a friend uses it on the Motorola Droid, each with Verizon (but again, be sure to ask before you buy the phone).