There are a few different ones out there. Obviously, VZ Nav from Verizon, but it's pretty much the same as Google Navigation, and you have to pay monthly for it. (You'd think since they can add it in for free with the $10 data package for basic phones, they could throw it in for us smartphone users too, but...whatever). There are others as well though, some of which you do have to pay for the app, or maps, etc. One that I have on my phone (I don't really use it tho, I stick with Google Nav when I use it), is MapDroyd. I have it simply because it allows for downloaded maps - I can download the maps onto the SD card for offline use. If I'm expecting to be in non-service or weak areas, I'll still have the map data, and won't have to worry about the mobile network. (I go Geocaching, so it could come in handy).
Another one, is Sygic. Looks like it's basically TomTom for your phone. It has a free 7 day trial, but looks decent, has good reviews. I haven't tried it though, and not sure what the actual cost would be after trial.
I just hit the market, and search for "Navigation" and it gives a few options
