In what way is a bicycle an improvement over a horse as long as the infrastructure for maintaining a horse already exists? I am sure it could have been built but why bother? A phonograph provides a service that would have been unknown at the time and is a much better plan to send back with your time traveller.
Horses must be bred, raised, trained (as does the rider), fed, watered, stabled, mucked, cleaned, saddled, and shod. Streets traversed by horses must be cleaned (the first urban transport pollution crisis revolved around horse and other draft animal dung, a/k/a "soil"). They're only useful for traveling so far, so coach roads and mail services (such as the Pony Express) needed frequent changing stations where horses could be switched and rested (every 10 miles for the Pony Express). Horses were a major expense and even during times when they were principle land transport were the privilege of the rich, or farmers who relied on horses for productive capacity.
Once built, a bike requires minimal maintenance, is vastly cheaper than a horse, can be ridden with minimal skill (and only the rider, not the bike, requires training), and can be stored in a house or small shed. Bicycle manufacture is highly amenable to mass production techniques (horses, not so much). Other than reinflating tyres and oiling chains, little maintenance is required. On good roads, a bike can easily be ridden 20-40 miles by even a cyclist of moderate skill, and single-day rides of 200-300 miles are attainable. Even loaded with camping gear, a bike can be ridden 60-90 miles per day, continuously, reasonably. Cargo bikes can carry substantial loads locally. Bike jitneys compete with horse-drawn vehicles for human carriage.
Horses or oxen, particularly teamed, can carry much heavier loads. In parts of the world, oxcarts, fitted with modern truck wheels and axles, still compete with automobiles for drayage.
You're right that bicycles are amenable to mass production techniques, but those weren't invented until the early 19th century at the earliest (specifically the invention of interchangeable parts and the 'American System' in the American arms industry). Realistically, these techniques weren't widespread until the last few decades of the 19th century.
This latter period is sometimes called the Second Industrial Revolution and is characterised by the invention of interchangeability, assembly lines, automated jigs for machining, and the use of electricity and non-coal petroleum fuels.
While the first industrial revolution produced coal and water powered machines, these machines were still themselves made by craftsmen. The introduction of interchangeable parts meant that it was no longer neccesary for a craftsman to hand fit the various components* together - you could make thousands of bicycle wheels and thousands of bicycles and fit them all together with almost no difficult to learn custom fitting. Automated jigs made it possible to mass produce standard sized parts.
(*) It's not even clear that the idea of a 'component' is a very useful one before interchangeable parts were invented because turning a barrel (even if it had already been bored), a stock, and various parts of the action into a rifle isn't something that a non-gunsmith can do. These were 'components' only in the sense that a felled tree is a 'component' of a timber house.
There's a video on Youtube of a gunsmith making a rifle the way it would have been made in the era of the American revolution - in the very early years of the first industrial revolution - and you can see how difficult and finicky it is.
I was answering the question of advantages of bicycles over horses, not on the feasibility of their production in ancient times.
That said, history is interesting.
Adam Smith's Wealth of Nations describes mass-production techniques, including specialization, special tools adapted to single sub-tasks, and a style of production approaching an assembly-line (work produced at stations, with the pieces moving from station to station. In 1776.
Modern mass production dates to 1803 and production of sailing blocks (used to raise and lower rigging on ships) in England, from which it spread to the US for clock and armaments manufacture. Eli Whitney (of cotton gin fame) attempted mass armaments production in 1798 but failed to achieve quantity output for another 8 years. Refinements in metalurgy, scientific management, steam and electric power, etc., produced further advances -- as with most developments, the seeds were planted early and incrementally developed over time.
As I note in another post, the two specific advances that really made the bicycle possible were advanced metalurgy and vulcanized pneumatic tyres. Both of these weren't particularly feasible until they actually emerged. That said, high-quality Damascus steel dates to 300 BC. The Greeks and Romans had and used coal (used in the production of both steel and synthetic rubber). Rubber was known as far back as 1600 BC, but among the Mayans in South America (it wasn't introduced to Europe until 1736): http://www.essortment.com/history-rubber-21100.html
But the biggest trigger for widespread bicycle adoption was probably socioeconomic, not technological. By the late 19th Century, a middle class with both discretionary income and free time had emerged. And though bikes were used for utility (commuting, errends, light transport), the real driver was recreation. The presence of intense socioeconomic stratification, slavery, feudal systems, and the like, had a serious damping effect on both creation and adoption of new technolgies and products.
Speed would be one. A horse can't maintain a fast pace for very long. A human on a bike can go much further than a horse can run in one day. That said, presumably the lack of appropriate roads would nullify that advantage.
This does not show that a man can go "further". It's about who ends first.
And even at that, the race started at 1980, but the first time a man on foot won the race was in 2004.
One "man on foot" win in 24 races and that man being a marathon runner, does not bode well with the idea that man in general can outrun horses for long distances.
It is rare for humans to actually be physically capable of it these days, but chasing animals until they collapse from exhaustion is something hairless sweating bipedal are built for. The very best horses could still do it, but attempting persistence hunting on horseback with most horses would probably injure the horse.
Of course horses have been selectively bread for endurance for thousands of years so arguably their achievements are human achievements, but that's beside the point. ;)
Assuming you could teach furniture carpenters to build bicycles from wood, the advantage bicycles could provide over horses would be cost. You don't have to feed it, and it would be cheaper initially too I am sure, at least after it gets to the point that you don't have to specially commission them. Horses used to be very expensive.
Over cheaper modes of animal transportation (donkey and cow?), the bike would probably have a speed advantage.
The real downside in both cases is cargo capacity and manual effort, but I think it could have made sense as a poor-mans transport. Barring that though, it could just be a toy for the rich.
At ~5 MPH for most travel, bikes wouldn't have had significant handling problems, though shock absorption on cobblestones would have been a bigger issue.
If you ever get up close and personal with a stage coach, you'll likely find the suspension interesting, though most in my experience are spring-loaded but undamped. There are reasons long land journeys weren't generally looked forward to.
I was thinking in terms of comparing riding a horse to riding a bicycle. I'm sure stagecoaches were miserable rides, but I don't think any kind of bicycle based technology would really compete with one.
