Whether it's a phone or a dedicated unit, for cycling you are best off figuring your own route out beforehand than using turn-by-turn navigation. It will make for a much more pleasurable experience. A bike specific routing algorithm that allows trails will likely take you down some muddy hell of a footpath, and a car specific one down some hideous dual carriageway or even a motorway, and avoid a handy alleyway cut-through. Much better to figure it out yourself first on a map, program that into the device and ask the device to follow that, or navigate by following a line by eye.
Plotting a route and turn-by-turn are different things I think. The turn-by-turn thing is where you're following a set route and you need sat-nav type instructions (i.e. left turn 300 meters, straight on at roundabout, head down dark alleyway and through kids adventure playground, etc...) These are the audio notifications I get from my phone using OSMand and they keep me on the route I had intended.
OSMand does have the facility to plot a route for you, using several different third-party algorithms but I generally build my routes in Endomondo or Google, or pick up GPX files from various websites.
GPS tracking is another part of the same jigsaw puzzle. OSMand can do it but I run Endomondo for that because it syncs to their website automatically so that my friends can see my routes and ride stats.
The final part is mapping. All the fitness type apps fall over here because they don't really have offline map facilities. Of the ones I've seen, this is where OSMand is best for me. They have freely downloadable maps for use offline, they're vector images so they don't fill you phones memory, and they are in layers, so for example you can download a map of all the Little Chefs, or a National Trust map and overlay it onto a road map.