How to make /sbin/shutdown, /sbin/reboot etc. require sudo again in 16.04?

Systemd does indeed handle the shutdown, reboot and other commands, and the default privileges assigned are permissive. To change this, you need to create a Polkit rule. Create a .pkla file in /etc/polkit-1/localauthority/50-local.d (say, confirm-shutdown.pkla) containing:

[Confirm shutdown]
Identity=unix-user:*
Action=org.freedesktop.login1.*
ResultActive=auth_admin_keep

The various shutdown, reboot, etc. commands are, in Polkit terms, actions in org.freedesktop.login1, for example, org.freedesktop.login1.power-off, org.freedesktop.login1.reboot, etc. The specific problem here is the default configuration, which is in /usr/share/polkit-1/actions/org.freedesktop.login1.policy:

<action id="org.freedesktop.login1.power-off">
        <description>Power off the system</description>
        ...
        <defaults>
                <allow_any>auth_admin_keep</allow_any>
                <allow_inactive>auth_admin_keep</allow_inactive>
                <allow_active>yes</allow_active>
        </defaults>

Note that it allows the active user to power off, reboot, etc.