We at NetToolKit have implemented arnath's requested functionality using OpenStreetMap data (demo available at https://www.nettoolkit.com/geo/autocomplete). The problem that we have found is that while some categories have great coverage (e.g. restaurants in Portland), many categories do not (e.g. gas stations). Assembling this data is expensive, and hence either the data is available via well-capitalized players (e.g. Facebook Places Search: https://developers.facebook.com/docs/places/web/search/) and/or are expensive to use (e.g. Foursquare).