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.