I haven't seen VZW's new navigation offering but I have tested TeleNav, Blackberry Maps & Google Maps on a Cingular 8800, 8700c w/puck, and 8703e w/puck. TeleNav is what you want. True turn-by-turn voice directions and large arrows. SAT acquisition was fast and screen refresh was very quick. It prompts you to turn or exit at 1/2 mile & 1/4 mile mark, well in advance of the actual turn or exit. It also re-routes you if you go in the wrong direction. Very nice.
VZW's offering is "suppose" to be a better VZNavigator. Sort of a TeleNav/VZNav hybrid or at least that's the rumor.
As much as I love TeleNav I'd stick with VZW. In my experience, I wouldn't trade VZW's coverage for Cingular's spotty coverage. If VZNav doesn't work as planned, you could always go with an external GPS puck and install TeleNav on the 8830. Your mileage may vary.