Может немного не по теме:
- неплохие карты с индексом улиц есть в телефонных справочниках.
Почти у любого местного жителя где-нибудь пылится пара-трока прошлогодних справочников, которые он с легкостью отдаст на растерзание, и из которых карты можно "ножечком-ножечком" отделить.
Карты достаточно детальные, но многостраничные. Общая карта города на одном развороте (примерно 2xA4) наоборот, не достаточно детальна.
- для велосипедистов в туристических киосках бесплатно дают большие раскладные карты с обозначенными велодорожками.
- также для велосипедистов очень хорошие, детальные, актуальные (и мои любимые) карты есть на
http://www.openstreetmap.org/ в качестве смотрелки для них хорошо подходит телефон nokia с программой
http://www.sports-tracker.com/ Но поиск по улицам в ней не предусмотрен. Нужно примерно знать куда едешь, а программа очень красиво будет показывать ближайшие велодорожки.