Both google nav and telenav download maps and routing info over the internet. I use google nav most of the time but if I'm traveling somewhere that I won't have a cell signal I use copilot (I think I paid $5 for it).
I haven't tried telenav simply because I have limited space left on my phone and I try to minimize the number of apps installed.
Copilot is OK, it's a little clunky and the maps are out of date but when I don't have a cell signal in the middle of nowhere I really like to have a working navigation solution.
As for google nav, I like the integration with other phone features... I can do a local search and right from the search results I can open google navigate to have it route me to the destination, also if I get a call while I'm driving google navigation will still provide voice prompts in the earpiece while I'm on the phone. The street view pop up when arriving at my destination is also handy.
I do wish google would add common gps navigation features to google nav... current speed limits, current speed, ability to customize the display to show eta, eta to next turn, current road name, lane assist for driving thru complex freeway intersections, etc.. They seem focused on adding more social integration features of late instead of adding navigation features.