(You need a jailbroken iPhone for this.)
xGPS is a navigation system which uses Google Maps for routing and display of the map. It can download map tiles for offline use and can use the "normal" map as well as the terrain map of Google Maps. Your current position is shown centered together with your route and you'll get turn-by-turn directions from a synthetic voice. It can recalculate the route if you get off it.
The first official turn-by-turn navigation in the AppStore. Currently only supports the USA. People living in Illinois might have to buy both parts (Western/Eastern USA; $20 each) as Illinois is split into two parts which were distributed on both maps.
Founded by previous Navigon employees, this app is not only really reasonably priced but also has always up-to-date maps. The only drawback is that you need a data connection (UMTS, WLAN) for it to work. So you should have a flat-rate plan for the areas you drive.
Both seem to be great but also expensive. IMHO if you prefer these two, buy a real device as it then allows you to make phone calls AND get to where you want.
If the iPhone would support Java Midlets, this one might be interesting. Completely free and based on OpenStreetMap. Maybe it would work with alcheMo, a J2ME to C++ converter. But if you have a "normal" phone with Java support and a memory card, this one is for you.