How to fix SSH errors when using Ansible with newer OSes like Ubuntu 16.04

Recently, as I've been building more and more servers running Ubuntu 16.04, I've hit the following errors:

PLAY [host] ************************************************************************************************************

TASK [Gathering Facts] *************************************************************************************************
fatal: []: UNREACHABLE! => {"changed": false, "msg": "SSH Error: data could not be sent to remote host "". Make sure this host can be reached over ssh", "unreachable": true}


/bin/sh: 1: /usr/bin/python: not found

The former error seems to happen when you're running a playbook on an Ubuntu 16.04 host (with gather_facts: yes), while the latter happens if you're using a minimal distribution that doesn't include Python at all. The problem, in both cases, is that Python 2.x is not installed on the server, and there are two different fixes: