The horse itself cost at least a third of a labourer’s yearly income (which was not really disposable), and that does not include a sufficiently large pasture or equivalent fodder.
Not only that, but those horses would have been work implements, like a tractor today, you would usually not get those horses out to go to church or see your family a village over. If only because most of the time the horse would be at work in the fields anyway.
"Regularly" may have been once a week (e.g., Lord's Day / Sunday). Otherwise people lived either in villages themselves, or in hamlets (collective security at night) and 'commuted' to their fields. Or on-site of the land owner if they were workers (earlier: serfs).
Living on a farmstead wasn't really a thing until relatively recently in history.
Also villages, churches, manors, inns, markets, blacksmiths, and all the other necessary infrastructure was rarely more than 1 hour on foot away.
In my country there's 1 church per 30 km2, that's on average 6km between churches which is roughly 1 hour on foot.
Serfdom declined over time in western Europe and had largely disappeared by the end of the middle ages. So it does not explain why western Europeans not invent the bicycle in that period that was at least a few centuries, sometimes longer - 800 years in some places!
They were too busy fighting wars, like the 100 years war. Also the Inquisition might not have seen bicycles with good eyes. The bicycle couldn't have happened without the Reinassance and the Industrial Revolution.
In general, in many cases, what rights exist on paper is irrelevant; what matters is how they are applied in practice, and what avenues to enforce their rights the holders have. E.g. it is not uncommon for societies with serfdom to limit the ability of serfs to file legal petitions against their owners.
I know there are reasons they didn't have bicycles, but I don't think "going by feet is equally good" is one of those reasons.