I’ve used OrganicMaps in the past, but for searching POIs and ahead route planning its just unusable.

Meanwhile i’ve found GraphHopper, an open source search, route and (experimental) navigation app from Germany. Great thing: its blazing fast! Check it out on F-Droid.