I agree, more people generating GPS traces outside towns would be good for open street map.
You're right about steps being fairly clear, but...
I think in marking "rideable" you end up wanting a lot of well defined tags to be able to see whether a route is: decent tarmac, sort-of-hard surface track, muddy / rutted path, this footbridge isn't rideable but still quicker and nicer than alternative ways of getting to the other side, this section is interestingly rooty on a mountain bike, just a little jump, here is an underpass that the local yoof get wasted in of an evening but is OK in the day etc. Somewhere in there you probably end up with opinion, or at least needing "type of bike" and a second opinion.
Sounds like an interesting tagging project. Maybe if we could carry accelerometers as well as GPS a scale of roughness could be automatically extracted. But, that's probably just because I could claim developing that as my day job