Natural problem arising from diagonalization? Diagonalization is a frequently used technique in complexity theory. However, the problems (sets) that are created by diagonalization rarely correspond to anything natural. It would be interesting to collect examples, when a problem was originally defined via diagonalization, but later it was found to coincide with a natural problem.
In some sense the halting problem satisfies this request (I was almost ready to say "There are no such examples!" when I thought of this one.) By doing diagonalization against computable sets, you can of course get sets of very high complexity, but the seemingly-most-natural way of diagonalizing against computable sets gives you a problem that is equivalent to the halting problem. As we now know, the halting problem is equivalent to many other computational problems, such as deciding many properties of TMs, telling whether a Diophantine equation has solutions, the word problem in finitely presented groups, telling whether a high-dimensional knot is the unknot, etc.

I am still ready to say that I would be surprised to see other examples (that aren't just, say, relativized versions of this).