From "English & American Tool Builders" by Joseph Wickham Roe, the text states that the earliest machine tools, those intended for precision machining of metal, and not wood working nor ornamental work, were boring machines. These were required for Watts' steam engine cylinders and the boring of cannons. The first such boring machine is credited to John Wilkinson of England for the boring of cannons. In 1775, he bored the first steam cylinder engine for Boulton & Watt. This machine was typical of its day in that most of the frame was made of oak timbers. Probably the first all-metal machine tool was built by Henry Maudslay of England in 1797. It was a screw-cutting lathe about 3 feet long. The need for scews and nuts in the building of other machines probably prompted Maudslay to build this lathe. Something that I take for granted is the ability to fasten objects together with a screw and nut which can be taken apart without breaking the parts. Before this, I suppose rivets were the principal method to join metal together.
The need for accuracy in these early machines could only be accomplished if straight, flat surfaces existed to check the machine components against. Maudslay did this by the production of surface plates which parts could be compared against for flatness. The surface plates were produced three at a time and rubbed against each other to show high spots which could be rough filed down by hand and then finished to minute precision by hand scraping. Two plates aren't enough as they wouldn't show the ball and socket defect that can slide over each other and show no high spots, yet not be true plane surfaces. Plates number 1 and 2 would be rubbed and scraped together until uniform. Then plate 3 would be worked to conform to plate 1. Now plates 2 and 3 are of the same shape, both are either a ball or a socket and when rubbed together will show their imperfection. These imperfections are scraped down and the process continues for all 3 plates until the ball and socket defect (concave, convex condition) is gone. As far as I know, this process is still used today and hand scraping is still a necessary part of machine tool building.
http://www.pioneers.historians.co.uk/maudslay.html
As for what came first, the lathe or the mill, the chicken or the egg, I would say it didn't matter. What came first was the hammer, chisel, file, and the hand scraper. Men like Maudslay could produce incredibly accurate parts with hand tools, great skill, and clever methods of obtaining accuracy.
As machines quickly grew in size, their own weight could flex their frames outside the tolerances demanded. To build a large lathe doesn't mean you need a surface plate just as large to make sure it is straight. Water in troughs set along a machine bed can be used to check how level the ways are. Straight edges can be used to check straightness of portions of a machine base and then the entire bed can be checked against water levels in troughs. Not until you approach 200-300 feet does the curvature of the earth start curving water levels to .001 inches. Wire stretched very tightly can be used to check straightness over many feet. Up until lasers, I have heard the wire method was used to check straightness of big machines of 100 feet and greater length. Ingersoll Milling in Rockford used wires, according to a guy I met that worked there, to straighten the beds of 100+ foot long mills.
Steve