The logic arrays do not physically transform when you program a FPGA. They get input from the program that determines their function.
The difference is essentially that with a normal CPU, the function is changed every time you load a new instruction. With FPGAs, you allocate a bunch of logic arrays to just one specific block of instructions all the time. That gives you the magic parallelism.
(The point is: you might argue that VHDL is just describing logic, but so is any other compiled code!)
> They get input from the program that determines their function.
Agreed, this is a program, yet this results not in software, but (configured) hardware.
> That gives you the magic parallelism.
And thus it follows that it's not magic at all, merely physics. Put an electric signal in, an electric signal gets out, and everything happens at 'once' (bounded by the speed of light and various other electronic considerations). This is what the essential difference is: hardware (however configurable, it is not software) vs software (however low-level, it is not hardware), and it is a very fundamental difference.