I'm interested in how much of the math and logic that we use in modern computer science was actually known or theorized about long ago, especially pre-1800s.
Particularly, I'm curious about things that are mostly or only practical to do with computers, but could be discovered by daydreaming and deriving without them. An example is the Diffie-Hellman key exchange, an encryption technique that allows two people to communicate privately with each other despite the presence of a perfect eavesdropper who intercepts every message sent between them. It's fairly simple to explain with pen and paper, but actually using it requires modularly exponenting extremely large numbers that would be ridiculous to do by hand.
Are there examples of ancient mathematicians/philosophers imagining that their work could be put to practical use if it were possible to do the computations at superhuman speed, then this ancient knowledge being implemented by computer scientists centuries later?
Plenty of widely used computer algorithms predate computers, but all the cases I can think of still had practical utility when applied manually (or with the aid of a slide rule or tables). Examples include Euclid's Algorithm, the Sieve of Eratosthenes, the Newton-Raphson Method and the Fast Fourier Transform (discovered by Gauss in 1805).
There's some room for quibbling about exactly what the first computer is. I don't think it's reasonable to argue that it's earlier than the tape-programmed Zuse Z3 (1941, German, and therefore relatively unknown) or later than the stored-program EDSAC (1949, UK). Given that Babbage's work was never completed and was pretty much ignored between 1870 and the 1940s, I'd consider work done before your 1940s First Computer of choice to be done before the first working computer. Quite a bit of theoretical work was done during this period, but I don't think it's really in the spirit of your question.
Very little of what we consider computer science per se was done before the 1930s. Lots of work done prior to that falls under various (other) areas of mathematics but is still very important to computer science. For instance, Boolean algebra (1854) gives rise to the boolean datatype in modern programming languages and gives the fundamental operations on bits that modern computers use, number theory (ongoing since ancient times) is important for compiler optimizations and cryptography, and the study of formal logic (the modern form was first published in 1879) is closely linked to the theory of certain programming languages.
The first things that today firmly fall under the umbrella of computer science rather than mathematics would be the work on David Hilbert's 1928 Entscheidungsproblem^1, which asked for an algorithm to decide whether a first-order logic formula is provable from the axioms alone. In 1931, Kurt Godel presented a proof that a sufficiently powerful formal system is either incomplete (unable to prove some things that are true and can be expressed in the system) or inconsistent (able to prove some things that are not true), which is considered very much in the spirit of computer science. Alonzo Church and Alan Turing's 1936 papers present two distinct but equivalently powerful systems of computation, and show that there are undecidable problems; problems for which no algorithm can always answer correctly, and are definitely computer science papers.