OsmAnd generally has decent routing if the underlying OpenStreetMap data is good.

Last I looked at it, the search didn't really support the obvious 'keyword near me' sort of query that most people are going to want to do.

Later: just took a look and it does a lot better. OSM POI data can be pretty hit and miss though.