One idea I had was what if during carriage travel you actually sit in the carriage and ride. Very RDR I know, but I thought if you ride in the carriage, any close by places you pass by could become "discovered" and it would allow for another side mission from time to time where your carriage gets attacked by bandits and you have to help defend it.
Any other ideas?