Why do complex numbers feature so prominently in quantum mechanics, when classical mechanics got by just fine without them?
Scott Aaronson gives this explanation, which revolves around the idea of wanting to assign a meaning to "negative probabilities":
I don't find this convincing, because I don't see a reason why nature should care about using one sort of probability over another. There's no physical gain from doing this, in the sense of enabling a universe that we can live in.
Rather, I would argue that the wavefunction has to be complex in order to have enough information to encode both position and velocity of particles into one function. A real-valued function works for position or velocity separately, but to have both in one function one needs the complex phase.
But why does one want to stick both x and p into one wavefunction in the first place? Here is where the "physical" benefit comes in. Having both x and p encoded into one single wavefunction partially removes their independence, by making them connected through the uncertainly principle. This has very profound effects at the microscopic level, and most importantly it allows things in the universe to be stable.
Let's back up for a second and try to imagine a world built entirely using classical physics. Atoms would then be like little solar systems - and this would be terrible because classical orbiting systems are all different, so no two atoms would be alike, and they are also generically unstable. For example, classical particles can orbit as close as they like to the center, so over time they will give up bits and pieces of energy (e.g., through weak interactions with other atoms) and gradually fall to the center. It would be completely impossible to evolve living creatures using this kind of inconsistent and unstable building block.
Similar problems afflict the classical theories of fields, in particular electromagnetism. There is an infinite range of frequencies, and classical physics allows each frequency to hold any amount of energy, however small. All the energy in the universe would then leak gradually into higher and higher frequency electromagnetic waves, and would become essentially useless. This is the so-called "ultraviolet catastrophe" which Max Planck was trying to solve when he discovered the quantum.
So, classical physics is just not suitable as the underlying theory for a universe that can support life, because its components simply have too much freedom. The particle motions are not constrained enough to form consistent and stable building blocks, such as atoms, and the fields are infinite energy sinks that drain away all available energy.
These problems are solved by quantum mechanics, and in particular what solves them is to encode position and velocity both into one wavefunction. Being entertwined in one function means they are not fully independent, and in fact the relationship is exactly the famous uncertainty principle (see e.g. http://www.letstalkphysics.com/2009/11/where-uncertainty-principle-really.html).
The uncertainty principle for particles means that squeezing a particle into a smaller space causes it to have higher velocity. Now remember the problem (one of them) with atoms in classical physics, namely that the electrons can orbit as close as they want to the center. This can't happen anymore because squeezing the electron close to the center makes it move faster, which carries it away from the center again. In other words there is a minimum size for the electron orbit - the "ground state" - and moreover its size and shape is completely determined by the uncertainty principle, hence is exactly the same for all atoms. This creates the stable and consistent building blocks needed to evolve life. (Of course things get more complicated for additional electrons and the higher energy orbits, but the principle is the same).
Now consider the electromagnetic field. Here the uncertainly principle implies that a mode with small wavelength ("squeezed into a small space") must oscillate faster, i.e., have higher energy. Again there is a tradeoff and the result is that for each wavelength there is a minimum unit of energy that it can transfer - the quantum. The smaller the wavelength, the larger the unit, and this prevents energy from dribbling bit by bit into that infinite pool of wave modes, because for short wavelengths the mode can only accept large chunks of energy at a time. Lesser amounts of energy are therefore stabilized and don't get drained way.
In short, it’s just very hard to build stable systems on a classical foundation because classical particles (and fields) have too much freedom. Hence the subject of classical chaos theory, which has no really QM analog. quantum mechanics solves this stability problem, and the complex-valued wavefunction lies at the heart of the solution. I haven’t seen any proof that QM is the *only* way to solve the stability problem, but I haven’t seen any other way either.