I had a trackball blackberry (Tour) for two years, and I was fairly satisfied with google's native Maps app [1]. While it doesn't include 3d navigation, it has routing, layers, transit, traffic, street view, and places -- just about everything the webapp provides. At the time (2010-2011) Google updated it every month or so with new features -- in that sense it was vastly superior to the iOS Maps app which google didn't control.
[1] http://www.google.com/mobile/blackberry/