While it wasn't quite as small or as fast as you'd be hoping for as it was built, the only thing between the mid-19th century and Konrad Zuse's Z3 and Z4 relay-based computers was the idea. In essense, it uses nothing that wasn't already in use by then: the word "relay" is just "telegraph" spelled weirdly (it was invented for telegraphy, and is simply the telegraph receiver driving another telegraph key); the Jacquard loom with its punched cards already existed, being a mere extension of the barrel organ and carrilon, which was in turn derived from a simple trip hammer; and the leap from there to perforated tape (for self-playing organs and player pianos) was buzzing in the air in the early 19th century and in place by the middle of the century.
All you need to build a relay computer from scratch is the ability to provide electrical current, to be able to create conductive wires and to insulate them, springs, hinges and to know about simple electromagnets. There is no fundamental technological reason why there couldn't have been a Tudor computer; people simply hadn't had a good enough reason to stick two dissimilar metal probes into a lemon to see if it made their tongues tingle or brought a compass needle (which they had) close enough to the contraption while they were doing it to notice the needle acting funny. All they were missing was some knowledge. Allesandro Volta invented the pile (battery) in 1800, mostly as a way to debunk Luigi Galvani's "animal electricty" nonsense. By the middle of the 1820s, that had led to Ørsted and Faraday discovering and developing electromagnetism to the point that everyone and his uncle Bob was inventing some kind of telegraphy system, and Morse's simple on/off system with an equally simple code was off and running before 1832 was out (though a more complex system was operating commercially before Morse's system). A system with relays in it was demonstrated in 1838. So, under 40 years to go from no continuous source of electricity to everything needed for a digital computer's hardware because of a skeptic's need to slap down a woomeister in scientist's clothing.
Charles Babbage rightfully gets a mention here, but not for his machines as much as for his central idea and impetus for creating them: that computation itself should, in principle, be subject to automation. It simply had to be, since human computers, even those using mechanical aids, made far too many mistakes. There were various arithmometers (mechanical calculating aids like the Pascaline or the 20th-century Curta calculator) already, but they still relied on the operator to do the mathematics - all they could do was a stage of the arithmetic. You needed to know not just which numbers to put in, but how to set up the operator and how many times to crank the handle, when to move the decimal point, etc. Then you had to write the answer out without error and hope the printer you gave the answers to set the type without error. The Difference Engines could only do one kind of calculation (sums of polynomials by the method of finite differences), but they were completely automatic after the "program" - the initial condition - was set up. The fellow cranking the handle only needed to know how to crank a handle. There are two working copies of Difference Engine Nº 2, and they do what it says on the tin. They caculate and print out the results and they create a stereotype mould from which a printing plate may be cast. The Analytical Engine would have been Turing complete, and a computer in the modern sense, but monstrously large, heavy, expensive and likely a nightmare to maintain. I'm just a little too old and unwell to expect to see it working in my lifetime, even as a proper mechanical simulation, but I do expect Plan 28 to become a real working thing at some point. But it's not the machine that's important as much as the ideas it embodies: function external to mechanism (lifted from Jacquard and his predecessors), working memory (storage other than on the cards), and conditional branching to enable iteration and recursion. But Babbage's use of decimal numbers, requiring great mechanical complexity, and his inability to see his machine as anything other than a programmable calculator mean that he's disqualified himself as the father of your practical, ubiquitous computer.
Binary wins for the same reason that binary won: everything is much, much simpler. Apart from the idea, that is.
George Boole and Augustus De Morgan had already lain the basis for, well, Boolean algebra by 1854, and the idea of binary arithmetic (which Boole's and De Morgan's work could handily automate the moment somebody noticed that it could) goes back at least to Gottfried Leibniz. (To be sure, binary existed before Leibniz, but its use seems to have been restricted to logic, philosophy, mysticism and - believe it or not - poetry.) To an unseemly degree, though, we are still dealing with mathematics in the sense of numbers. And to anybody working with pencil and paper, binary is an awful lot of ones and zeros and chances to make mistakes. Boolean algebra may make sense for logical problems, but without computers (or something very like them), it's just something nice to discover and file away in the annals of mathematical academia when it comes to arithmetic.
For anybody paying attention, though, Ada King, the Countess Lovelace - who had been tutored by De Morgan - had already made the distinction between computing as we understand it today and mere mechanical calculation in her rightfully famous translation and considerable expansion of Manabrea's Sketch of the Analytcal Engine invented by Charles Babbage. She was talking about a machine that was largely hypothetical, but whose operation was fairly well understood. (That is, what it did was fairly well understood; how to build it so that it does that without breaking while using only the power of a modestly-sized stationary steam engine, keeping within the budget of a wealthy nation and taking slightly less time to build than a medium-sized Gothic cathedral was a different, somewhat harder question.) She had been an acquaintance and sometime friend of Babbage's since she was 17, and was in contact with him while writing the Sketch. Her assertion that a machine of that construction could be used for almost any purpose was astonishing - she recognized that while the machine could only operate on numbers, those numbers didn't have to represent numbers. They could be anything: letters of text, notes of music, colours of a picture - anything that could be represented concretely - and that, while the operations were, strictly speaking, additions and multiplications and such, they could have and necessarily would have different meaning when applied to these numbers-as-metaphor. When looked at one way, that's just saying pray, Mr. Babbage, why can't the pictures from Mr. Jacquard's loom still be pictures in your machine?, but she went deeper than that - about a hundred years before Turing.
All this to say that the technology itself was contemporary with the late Georgian and Victorian period, the ideas were in the air, and the critical insight - using numbers to represent entities other than quantities - was there to be seen by the first person to have a good reason to notice it. Have the right random Belgian sneeze at exactly the right time on a particular Tuesday morning in 1798, just hard enough to have someone next to him spill his coffee in a particular way, causing... and all of a sudden you have Turing-complete binary relay computers by 1820 or so, and wonderfully miniaturized versions running at a reasonable clip (think early vacuum tube mainframe speeds, not today's) only a few years later, even before the incandescent light bulb has been invented. Using such machines to control the gearboxes of armies of clockwork servants is left as an exercise for the reader.
