For UK Rights of Way, another way to go is to make GPX files. RoW data for most counties is freely available, and there's an excellent guide here:
Using JOSM (maybe also QGIS if you go to the original source and discover it is WFS or something peculiar) you can export as GPX. What I then do is use GPSBabel's "crosstrack" simplification method with an error bound of 5m to reduce the file size (actually I use the program "Viking" which is a friendly front-end to GPSBabel and select filter>compress). All the tools I have mentioned are free.
For example, the GPX RoW for West Sussex is 12,463 kB but after simplification with a 5m tolerance it's only 4,295 kB. And that's a big county. On my old phone I have GPX RoW files for the three counties I visit most without any trouble.
OsmAnd gives great options for how a GPX is displayed - this is really quite a nice way to do it!