I'm going to be looking into OSM because of comments here. I've also looked at MapBox but last time I tried the mobile web experience was basically unusable (although Google Maps isn't great either).
(Sorry, rereading what I wrote makes it sound pretty slanderous). Not sure if you'll be doubling back on this, but I thought I'd respond anyway. I was talking about the mobile web experience, specifically on Android.
I was playing with the MapBox SDK roughly a year ago and I remember having a lot of trouble at the time panning and zooming. This was on a Droid X. So gave up on it at the time, even though I thought the desktop experience was so great.
Anyway, I just tested again, and whatever I was seeing before is not there. I'll give MapBox another shot.
Do you have other suggestions?