GPS Review has a huge, in-depth review of AT&T Navigator for iPhone, which costs $10/month and downloads its maps over a network connection. The latter point has some positive and negative implications:

[T]his means that the application relies on network availability for the app to work. Should you find yourself starting a trip in an area without network coverage you are simply out of luck until you drive to an area with network coverage. However I didn’t experience any issues while driving into an area with in and out network coverage — the app downloads maps ahead of time to help prevent that type of issue. Also your phone will spend more time using the network downloading maps as you drive along. This also seems to have a negative impact on battery life.

But downloading maps over the network does have one advantage over your usual in-car GPS unit: the maps never need updating.

Want a map update with a typical PND? That might set you back $50-$80 per year, but map updates are “included” with AT&T Navigator since the maps are not on-board and are downloaded to your phone as needed. Want live traffic reporting on your PND? While there are free options that are advertising based, other paid options can cost around $60 per year.

Previously: iPhone/iPod Touch Application Roundup.