Telenav is good, until you get a phone call when you are in the middle of no where. When you answer, your maps are gone (uses a data connection to navigate). Same with google maps and live search. IF you plan on using your phone while you are navigating, you need to have the maps on your phone.
That being said, TomTom, Garmin and Igo would probably be your best bet.
I like Garmin because it has the google search built in, eliminating the need to constantly update your POIs. Only problem is that it lags worse than TomTom on the Touch Pro
TomTom, while it is not as versatile as Garmin, runs better on the TP and will not have you missing turns.
Test a few out and go for your favorite!
-s