To the best of my knowledge, the two major breakthroughs in regarding negative
results in computation/recursion theory came in 1936 by Church and Turing.
They both prove that some variant of the Halting problem was undecidable.
However, a very simple proof of the statement "There is an undecidable problem"
already existed at that time, namely the fact that there are simply too many
problems and too few algorithms.
Assuming that any algorithm has a finite description, and that they take natural
numbers as input, we are trying to make a bijection between the natural numbers
$\mathbb{N}$ and its powerset $2^{\mathbb{N}}$.
Adopting Cantor's diagonal argument to Machines, we can observe that if
$\mathcal{M} = \{M_i \mid i \in \mathbb{N}\}$ is the set of machines, and for
every machine $M \in \mathcal{M}$, that $M(n)$ is either yes (halts) or no (does
not halt), for $n \in \mathbb{N}$.
Then we can construct the set
$$U = \{i \in \mathbb{N} \mid M_i(i) \text{ is no} \}$$
like Cantor would, and pick the $i$ s.t. the domain of $M_i$ is $U$, and ask
whether $i \in U$, in both cases reaching a contradiction.
Question: Why wasn't this discovered between 1875/90 and 1935? (Or was it?)
Best Answer
The argument you sketch could not be discovered until one had a sufficiently formalized understanding of what "a recipe for computation" even means to be able to argue that there are countably many of them.
Such an understanding had been brewing slowly in the first decades of the 1900s, fueled mostly by foundational considerations -- but it doesn't really seem to have been until the 1920s that people began to seriously consider that perhaps they shouldn't be thinking in terms of "what is the way to do such-and-such?" but in terms of "is there any possible way to do such-and-such?" And before the latter question gets asked there is no real interest in getting all pedantic about what counts or doesn't count as "a way".