Nokia has announced their mapping service, Nokia Maps, is now available for iOS and Android. It was actually launched as an HTML5-based web app. You can check it out at m.maps.nokia.com.
It does mapping, navigation (walking, driving, public transportation) and even audio directions. However, those currently only work while walking. It may not work as quickly and nicely as a native app, but it can do the job.
It works on mobile devices like the iPhone, iPad, iPod touch and Android devices on 2.3 or higher.