Update: Extra libraries do not need to be installed. IntelliSense can operate using only the headers installed by the Arduino app, but a few others may help. More updates below.
When VSCode builds, it uses the SDK. However, IntelliSense cannot read the SDK files to operate (as far as I can tell), which throws these annoying errors and eliminates most code completion capabilities.
Both includePath and browse.path need to be configured. includePath does not include recursively (but that feature seems to be coming soon). browse.path is recursive, but including the exact location of header files is in includePath is still necessary for IntelliSense features. browse.path will use the Tag Parser to provide tools such as the "lightbulb" that you can click to help resolve your includePath issue. (Source: What is the difference between "includePath" and "browse.path" in c_cpp_properties.json?)
Mac:
avr/pgmspace.h is located at: /Applications/Arduino.app/Contents/Java/hardware/tools/avr/avr/include/avr/pgmspace.h. It's coded into the libraries as avr/pgmspace.h; for this reason, we need to include the path that avris located in.
2. Edit c_cpp_properties.json:
"includePath": [
    "${workspaceFolder}/libraries",
    "/System/Library/Frameworks/Kernel.framework/Versions/A/Headers",
    "/Applications/Arduino.app/Contents/Java/libraries",
    "/Applications/Arduino.app/Contents/Java/hardware/tools/avr/avr/include",
    "/Applications/Arduino.app/Contents/Java/hardware/arduino/avr/variants/standard"
],
"browse": {
    "limitSymbolsToIncludedHeaders": false,
    "path": [
        "/System/Library/Frameworks/Kernel.framework/Versions/A/Headers",
        "/Applications/Arduino.app/Contents/Java/"
    ]
},
"forcedInclude": [
    "/Applications/Arduino.app/Contents/Java/hardware/arduino/avr/cores/arduino/Arduino.h"
],
Windows 10:
2. Edit c_cpp_properties.json:
Revise includePath to look like this:
"includePath": [
    "{$workspaceFolder}/libraries",
    "C:/Program Files (x86)/Arduino/hardware/tools/avr/lib/gcc/avr/5.4.0/include",
    "C:/Program Files (x86)/Arduino/hardware/arduino/avr/cores/arduino",
    "C:/Program Files (x86)/Arduino/hardware/arduino/avr/variants/standard",
    "C:/Program Files (x86)/Arduino",
],
Alternative Method (probably a bad idea):
If you can get a version of any missing library, you can probably put in in your libraries folder of your project if your includePath includes "${workspaceFolder}/libraries". Make sure to namespace your libraries appropriately, e.g. libraries/avr/pgmspace.h. I have not tested this method.
Updates: 
- Changed from home.path to includePath. See more here: vscode-cpptools/FAQ
- The tools downloaded by the vscode-arduinolibraries are not necessary on Windows 10.
- Changed Windows config paths to use forward slashes instead of escaped backslashes.
Source and further tips: Enabling Arduino Intellisense with Visual Studio Code