"Java runtime could not be located" when starting VSCode with the Salesforce Extensions

There are explicit details on the steps required for this in How do I configure the version of Java that the Apex Language Server uses?

By default, VS Code attempts to locate your local Java installation by looking for a JAVA_HOME or JDK_HOME environment variable on your computer. If VS Code cannot find your Java installation, or if you want it to use a different installation, change the salesforcedx-vscode-apex.java.home setting.

Note that while the message specifies the JRE the prerequisites are currently for the JDK.

{
    "salesforcedx-vscode-apex.java.home":
    "/Program Files/Java/jdk1.8.0_121"
}

Upon restarting code.exe wanted network access past the firewall.

The output window for the Apex Language Server also showed messages indicating it was running now.

Not sure but you need java 8 specifically. Doesn't seem to work with Java 11. I ran into the problem and found that the required version is mentioned in these issues and comments on GitHub.
https://github.com/forcedotcom/salesforcedx-vscode/issues/100 https://github.com/forcedotcom/salesforcedx-vscode/issues/930