Подумайте, какая карта вам больше подходит, найдите все места, которые вам нужны. В США и Европе Google, Bing, Yahoo имеют довольно похожие карты. Однако если вам нужны другие страны (в Азии, Южной Америке, Восточной Европе, Африке), единственным ответом будет OpenStreetMap.
Об API. Наиболее мощным и гибким является OpenLayers, он позволяет подключаться к различным картографическим сервисам. Однако это немного медленно и сложно.
В противоположность Google API быстрый и маленький, однако он привязан к Google Maps.
Если вам нужен API-интерфейс, связывающийся с данными OpenStreetMap, попробуйте Cloudmade.
Тем не менее сначала выберите карту, а затем выберите наиболее естественный API для нее.