It's a Pandora's box you just opened buddy. My general snippets of impressions distilled down to stereotypes from using pretty much all the major apps in the market.
The common things are: Routing is about on par across the board these days. Most support Google local search in the app itself. TTS is getting very common as well.
MotionX - Cheap (subscription based). Gets the job done. Depends on a data connection to route. Can cache some tiles that you pick, which can help, but it sucks down time. UX is a bit busy in some areas, making it feel crowded when it really isn't.
Garmin - One time cost. Depends on a data connection to route, uses Navteq data. It's pretty much the Garmin UX you expect, but designed around cell phones that have a data connection. Will cache the tiles needed for the route, but you need data to create a new route.
TomTom - One time cost (Traffic is a subscription). Most consistent and polished UX of the bunch, IMO. Wide feature set aimed at letting you fine-tune routing is nice and has good map browsing, but lacks the ability to do waypoint navigation (only supports 1 destination and a via).
Navigon - One time cost. UX is a bit rough, but uses Navteq maps and has a large feature set. Additional features aren't subscriptions, which means you can get what you want for a fixed price. Weather, Traffic, and advanced map data are available as extra.
Magellan - One time cost. Navteq data. Free Traffic. New 2.0 UX fixes a lot of issues it had before, and now has one of the most robust 'navigate to contact' options out there. Minimal feature set compared to the others, but what it does do, it has learned to do well with a decent map view UI. Can be crowded in landscape though.
In my own experience, TomTom comes in first, but I'm just as picky about my UX as I am the feature set. The most annoying thing is the map data is outdated right on my street (Microsoft has been doing major construction). It's a bit odd Telenav hasn't updated it in years.
Magellan is currently my #2, with the release of 2.0. Before 2.0, I would have ranked it below Garmin and Navigon, but the UX has come a long way, and the contact navigation is pretty much spot on unless it's in an area of recent construction and the road isn't in the map database. Needs better options to enter in a destination (lat/lon), and a better map browser that doesn't hide too many roads at at once.
As for Navigon, the only thing that really bugs me is that the one thing I want to customize (the routing) is the area it gives me a bunch of choice based on what they think I want and not a lot of good ways to tweak the routing behaviors beyond that (something TomTom is really strong at). The UX is rough, but workable, and is really what drives it below my #1 choice.
