Thanks for your detailed response. Primarily, I just need something that can re-route on the fly if necessary. I shall be riding a recumbent trike, so don’t really want to be restricted to cycle paths alone, as lots of them are little more than single-track dirt paths, too narrow for a trike. Don’t need calories, ascent and all of the other trimmings, as I shall be touring rather than training or racing.
OK!
That changes things, so.

In that case, I'd be less critical of Google Maps because you probably wouldn't be using their cycling routing - you'd be selecting smaller roads.
How do you plan routes currently? If you use any existing cycling navigation sources is there not a risk that they can send you down "bike" paths that would not be suitable for your setup?
I just need something that can re-route on the fly
When you say this, do you mean that you want to keep your original destination (say, in the event of a detour?) or do you want the flexibility to change your destination on the fly?
If it's the former, then my limited experience of the likes of RideWithGPS etc. is that they vary in their ability to reroute you (ie turn left to get back on course) or to recognise when you do get back on course without a data connection. The best way to proceed is to test each one out by plotting a route and going off course.
If it's the latter, then your options are very limited as just about every app needs a data/wifi connection to process a route.
I tried the Garmin touring and found it to be totally unusable for touring. Poor battery life, incompatible with hub dynamo, behaved erratically when off course, too slow to navigate in cities and crappy customer service. And for your needs, it may not be suitable because it will only consider bike routes meaning you could end up on singletracks.
In my experience, OSMand is the only one to do this.
But, like I said, it's a bit slow & clunky and in your case, if using the cycle routing option, there is always the risk of ending up on surfaces not suitable for you. I can't speak for how well it will select minor roads.
I'm a cycle tourer too and did a fair bit of research on this a few years ago. I was looking for a gps/navigation app/device that would let me create a route from start to finish, on the fly and follow it.
The fact is, that without wifi/data there is nothing out there except OSMand.
And I've used OSMand for years as my emergency back-up on a tablet. It does that job perfectly, if slowly (so long as I have the maps downloaded). I haven't really used it as a day to day navigator except when I was testing it out.
It seems to me that you have a very specific set of needs and I'm not sure that bicycle navigation is necessarily what you are looking for.
It seems to me that navigation on back roads and minor roads is really what you are looking for and being able to add in bike paths (where you are 100% certain of the type of surface).
While that is doable on a P.C., it becomes much harder on a phone, forgetting about the connectivity issue for the moment. A tablet may be easier.
FWIW I settled on a Wahoo Elemnt for my navigation needs. It works in conjunction with my phone - no computer needed. I create my "routes" on a variety of different sources -
http://cycle.travel/ is one of my favourites, but I've also used RideWithGPS (really good for finding routes created by other cyclists - might be useful for you to search recumbent or trike) and a few others. Then I send the gpx or tcx files to my phone, then to the unit.
The truth is, I hardly use it for navigation, preferring to wander as I go along. The exceptions are when I need to be somewhere, for example, campsites are few and far between in winter - I'll aim for my "route" and follow it to the end.
If I need to, I can take out my OSMand tablet, do up a new route, bluetooth it to my phone and from there, bluetooth it to the Elemnt. However, to process the route, the phone needs data/wifi.
Wahoo told me a couple of years ago that they were going to change that but it has never happened.
If they did, it would be a real breakthrough in bike navigation, in my opinion.
If it was me I'd question why I'm getting the Garmin.
I'd do a little research and look at a decently robust tablet with a decent mount and the difference in budget between the Garmin & tablet would let my buy a fair whack of data on disposable simcards or cups of coffee in wifi enabled cafes.
I'd also suggest asking in recumbent or trike forums as well as the electronics forums, as well as researching general gps navigation apps. Like I said, your needs are not necessarily in line with most cyclists.
Good luck!