If you are looking for just Geocoding and reverse geocoding you could check out tinygeocoder. I haven't used it myself, but it could be an option to review.
For your iOS project you could use Route-Me (link). This is an open source framework that pretty much provides the same functionality as MapKit, but allows to integrate different map sources (e.g. Open Street Map, Cloudmade etc.). As far as I know, this is the only alternative you have on iOS.
For Android, there are various alternatives that allow you to use alternate map sources. See this link for a good list of options.
Great list of alternatives to Google Maps being generated here. Good question. Not sure about your appliation - but one more from Nokia - Ovi Maps http://api.maps.ovi.com/ . They have some excellent data (they own Navtech) and incredible 3D visualization.
Some location-based APIs (not map tiles) - don't know if it would be useful for your project - travel time calculations, public transit data and walkability (Walk Score) for maps.