Your desires are mutually exclusive. A phone (or watch) needs to be within cell service. So there is the device cost, and the monthly service cost.
"Trails" can mean poor or no cell service. So that means a full GPS that can see many satellites as well as have off-road maps loaded. Likely a Garmin self contained unit, that runs about $300. I can't speak to the ability to "route to home" using trails (vs streets and bike paths), that will require some more research. But my guess is that even the best only show long established well-known trails, and not recent smaller ones that spring up. Which at best may still have him in a situation of "go south" - but which way to avoid that big hill, canyon, or other...