>download a gigantic runtime, deploy a specific version of the JVM
That's not true. JVM is incredibly backwards-compatible, up to the point it becomes excessively so. That means you simply need a recent enough version of JVM.
>make the whole thing run in a sensible way for end users without having to type an arcane command. A configuration nightmare.
That's partially true. Java launchers are system-dependent, though WebStart helps somewhat.
But it's the same problem with Python, you have to package a Python app separately for Linux, Windows and Mac OS X.