Connectivity matters--but so do looks
Storage-based navigation apps provide you with most if not all of the data you need to confidently navigate almost anywhere. However, they require a great deal--a minimum of up to 10%--of your total storage space for all of their data. Connectivity-based navigation apps are easier on the storage requirements, but require a reliable, high-speed cellular Internet connection.
That said, in my tests having North American or U.S. map data on my iPhone 4S wasn't an issue for me--I had plenty of room left over. Neither was connectivity a problem, at least in well-covered metropolitan areas and on well-traveled U.S. interstates. In Chicago, for example, my carrier, T-Mobile, gave me reliable coverage, and I've got plenty of 4G goodness via my Sonic 4G Wireless Hotspot. But on weekends, or when I didn't have my hotspot handy, navigation via connectivity-based navigation apps didn't always come through. Although EDGE on an iPhone is OK for most non-data intensive stuff (status updates on Twitter and/or Facebook, texting, calls, etc.), staying inside a 3G/4G coverage area is needed for connectivity-based navigation solutions.
At the end of the day, which app is best for you can be a coin toss. How much you like the navigation screens also matters a lot. Pick the one that not only performs well, but seems like it would be the most visually appealing to you. This thing is going to be running in your car, talking to you, for probably as long as you have your iPhone. No matter how accurate it is or how well it performs, if you don't like the app you won't use it.
As a final point, if you do decide to go with a connectivity-based navigation system, you should think long and hard about whether your intended route will support a signal, whether you're going out of state or to a local but unfamiliar area. Having your map go out on you due to lack of signal isn't something that gets covered in any app's user manual, but is something you'll want to avoid. Check your coverage area before you start out, and make sure you're going to have the connectivity you need. After all, if your GPS app isn't there for you when you need it, why have one?