I would suggest osmand. The basic version is free, you can download data state by state (country by country when you are traveling) so it doesn't need a data c

I would suggest osmand. The basic version is free, you can download data state by state (country by country when you are traveling) so it doesn't need a data connection on the road (but online search is available if you do have a data connection). It does routing for cars / bikes / pedestrian and has decent turn-by-turn instructions that you can configure to your liking. The underlying data comes from OpenStreetMap (hence the name of OSM + and(roid)), so if the data is wrong you can fit it yourself.