I've used VZNavigator on all my Verizon phones and it was one of thethings I missed most (aside from the EVDO and better connections) when I moved to AT&T. I tried Telenav on my Palm Treo 680 and was not impressed at all.

VZNavigator somehow managed to work well enough to not need a dedicated GPS. Unsure if it's the netowrk, the handhelds or just the software itself. I've tried several thrid party GPS utilities on my Treos and finally gave up. My Christmas present this year is a Garmin Nuvi 750.

It's sitting on the desk behind me and if my husband doesn't wrap it soon there's going to be an empty box under the tree and a GPS unit in my car well before Dec 25 :P