I recently found that the OsmAnd app lets you adjust the safety of your bike routes, so you can prefer safety over distance.
When navigating, click the "Ride Style" button and choose "prefer unpaved roads." That name made me think it would find gravel/off-road trails, but it actually selects safer roads. In my experience this setting chooses the optimal routes--it's finding the same general path that I would pick based on local knowledge, and it found improvements where I could take a slightly different street for a few blocks to avoid cars!
Also, OsmAnd~ is available via Fdroid with all the paywalls removed.
I think the main thing for me in osmand was to uncheck "fastest route" option somewhere in the navigation settings. That was some terrible routing before i found out about that.
However i have been using brouter as the routing engine in osmand and never went back. You can use the brouter profiles from f.e bikerouter, or create your own. Haven't used the osmand internal engine in years so not sure how it developed in the meantime. You lose some details in osmand, road surfaces i think, but not important to me, i see it on the map, super happy with brouter engine.