Classical electrodynamics is deterministic. QED is indeterministic, or probabilistically random. Yet they agree with each other? What am I missing?
Classical electrodynamics and quantum electrodynamics don't agree with each other in general. They are distinct, inequivalent theories. Your observation that classical electrodynamics is deterministic, unlike QED, is one sufficient proof that they're inequivalent.
At most, the expectation values of some observables in quantum electrodynamics obey the same equations as the equations obeyed by the corresponding classical quantities in classical electrodynamics. Whenever this is true, it may be proven simply by inserting the Heisenberg equations of motion of the quantum theory to the expectation value brackets, $\langle \dots \rangle$.
But this doesn't even hold for the general operators because $$\langle X\rangle \langle Y \rangle \neq \langle XY \rangle$$ So if you first replace the quantum observables by their classical counterparts and then you multiply these classical quantities, you get a different result than if you multiply the quantum observables first and then you compute their expectation values! For this reason, most of the nonlinear equations of motion in a quantum theory disagree with the classical theory even at the level of the expectation values!
The linear equations, like Maxwell's equations in the vacuum, agree in the sense of the expectation values. But quantum theories are not just about expectation values. Quantum theories probabilistically predict lots of things that aren't included in the classical theory at all.
QED and classical electrodynamics also happen to agree in some formulae for various cross sections in simple problems etc. (when the QED loop processes are ignored). Those agreements are sort of coincidences arising from the simplicity of the theories and integrability (solvability) of these simple problems.