Why is the Deutsch algorithm faster on a quantum computer?

On a classical computer, you can recycle memory, so there is no need for storing all intermediate results. The main source of the higher performance of quantum computers is the possibility to do an operation with all different values you can store in n q-bits register at once. However, this is not a case always. For example, the evaluation of Boolean function parity has the same complexity both on a classical and quantum computer.

Deutsch's algorithm is not faster on a quantum computer, Deutsch's algorithm is only possible on a quantum computer.

A classical computer cannot perform Deutsch's algorithm, it can only simulate Deutsch's algorithm. Forget about speed, more fundamental is that we are performing a type of computation that can never be performed, in any amount of time, by any classical system.

Consider the case of two possible evaluations, $f(0)$ and $f(1)$. In any classical computation these evaluations are mutually exclusive. We can design a classical system that evaluates $f(0)$ or $f(1)$ probabilistically to simulate Deutsch's algorithm, but any given evaluation is either $f(0)$ or $f(1)$. Evaluating one means we did not evaluate the other.

In contrast, Deutsch's algorithm is not evaluating $f(0)$ with some probability $p$ and $f(1)$ with probability $1-p$, this is only the outcome that we can simulate classically. In Deutsch's algorithm the two evaluations $f(0)$ and $f(1)$ exist simultaneously (in superposition) and interfere with each other.

I suggest forgetting about performance until you have a very clear understanding of the fundamental difference between a quantum algorithm and a classical simulation of a quantum algorithm. In other words, until you have convinced yourself that Deutsch's algorithm can never be performed by a classical computer.