Consequences/existence of problems without any "optimal" algorithm
Blum's speedup theorem, proved in 1967, shows that there is such a problem $P$ that has no optimal algorithm.

The problem $P$ doesn't look all that much like addition or graph coloring - it's defined in terms of sets of machines $Z_i$, the primitive recursive functions $\phi_i(n)$ computed by the $i$th machine, and "step-counting functions" $\Phi_i(n)$ (which count how many steps the $i$th machine took to execute its function), and involves search over the latter in order to achieve the desired properties :).

It's a good reminder that the space of algorithms is large and counterintuitive - especially when the inputs and outputs are themselves programs. But you're also not likely to see this sort of weirdness until your inputs are programs, either, and maybe not even then depending on what you're trying to do with them...

Reference:

Blum, Manuel. "A machine-independent theory of the complexity of recursive functions." Journal of the ACM (JACM) 14.2 (1967): 322-336.