By reducing the step size, I can actually get my naive road-follower to do a better-than-expected job of following curves: I'm guessing that this is because roads are more self-similar than what surrounds them, so looking for linear self-similarity stays on the road. What it does NOT do, however, is find the middle of the road. Look closely and you'll see that the path drifts over to one edge of the road and stay there, then wanders back again.
This makes sense; road edges have the same linear self-similarity as road centers, so it's just as happy to follow an edge. But, for OSM we don't want edges. How to tell it to stay in the "middle"? Currently each next point compares the image from the previous point. This makes it largely immune to gradual changes (like the road becoming unpaved, or wet, or shadowed, or newer/older pavement, or even aerials taken at different times) but it allows it to drift to one edge or the other. We could compare to the initial (centered) point, which would solve the drift, but that would to fare poorly if the road's coloration changes over its course.
It will also need some criteria for deciding the road has ended. We can't use an absolute similarity value, since it will vary from place to place. Perhaps if we assume that the initial stretch of road is good, then that calibrates our expected similarity; anything that is e.g. 50% less similar than that can be considered "probable end of road".