Map tiles should almost be a canonical example of a ridiculously parallelizable problem. Even if the data access itself is your bottleneck, you can fix that by simply bringing up multiple servers and replicating it.
Unless your map data is so dense that it takes over nine hours to generate a single tile, you can always scale the work out. It's only a matter of justifying the organizational time and whatever expenses are incurred for the extra equipment.
I had intended to make as much of the app cross-platform as possible, so I was predisposed to use HTML5/JS in the first place- 95% of the app will be directly transferable to Android. I'm also not sure if you can use custom map tiles with the native map control in iOS- I've certainly never seen anyone do so. Although I'm not yet taking advantage of it in the app, the ability to cache map tiles locally is also a great plus.
I'm extremely happy with the end result- it really does work as well as the native map control. In fact, I found a demo here:
http://leaflet.cloudmade.com/examples/mobile-example.html
It's a little more work to get it looking as good, but nothing some CSS3 can't fix (box shadows, rounded corners and the like). The story is a little different on Android as pinch-to-zoom doesn't work, but I think that's a WebKit flaw, rather than a leaflet.js flaw.
https://github.com/mapbox/route-me https://github.com/mapbox/mbtiles-ios-example https://github.com/mapbox/tilestream-ios-example
The main advantage over JS is the ability to go offline, as well as performance. But that's largely negated if you need to go cross-platform as you do, where I think JS does make a lot of sense.
So I ripped the whole lot out and replaced it with some custom TileMill-built map tiles and CloudMade's leaflet.js mapping library. It looks ten times better, works like a native map, and I can even control things like local caching of map tiles, which the Google licenses restrict you from doing. I have the tiles served from an EC2 instance running TileStream, and a CloudFront CDN to cut down on costs- it works great.
That said, it isn't for everyone- I'm lucky in that my app currently NYC-specific, so I only needed NYC map tiles. Those alone took ~9 hours to generate (x2 for separate 'retina display' tiles). I dread to think how long generating a whole world would take.
There's a preview of the tiles here, if anyone is interested: http://www.taxono.my/ . The process isn't quite seamless yet- there were some bugs related to street labels that I couldn't fix (and appear to be related to the underlying Mapnik library). This post has reminded me that I really need to write a full rundown of my experience, but in case you couldn't tell, I'm impressed.