vz navigator is offered on some of their android phones, and available as a download on others. My wife's droid 2 today came with a new software update,that preloads vznav onto her phone.
re: gps, yes google cut a deal with vzw to let them use their software on the vzw network.
however some of their newer blackberries and winmo 6.5 phones have functioning gps as well...it was a long struggle but vzw finally opened up gps for them in 2008.
I do know vzw and microsoft have some deal to install bing and bing maps onto some of their phones, including winmo and some android devices like the fascinate. Maybe hp can cut a deal with their long time partner microsoft to include bing maps with navigation on future webOS phones? Just a thought.
yes google maps is better, but bing maps is a pretty good alternative.