GCC5.4.0 stdio.h: No such file or directory

Question

A new Linux box was given to me with a Non-GUI version of Ubuntu 18.04.1 already installed, however, it seems to be stuck in a weird state that I've never encountered before...

I've tried compiling the quintessential Hello, World program using gcc with the following result:

#include <stdio.h>
int main() {
    printf("Hello, World!");
    return 0;
}

test.c:1:19: fatal error: stdio.h: No such file or directory
compilation terminated.

I've tried the suggestions posted in another question: C stdio.h no such file or directory but with no luck.

Reinstalling gcc-5, and running sudo apt-get update did not solve the issue. When trying to install build-essential I ran into a surprising amount of build dependencies that would not install.

ubuntu@ubuntu:~$ sudo apt install --reinstall build-essential
Reading package lists... Done
Building dependency tree       
Reading state information... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
 build-essential : Depends: libc6-dev but it is not going to be installed or
                            libc-dev
                   Depends: g++ (>= 4:5.2) but it is not going to be installed
                   Depends: dpkg-dev (>= 1.17.11) but it is not going to be installed
E: Unable to correct problems, you have held broken packages.


ubuntu@ubuntu:~$ sudo apt install --reinstall build-essential libc6-dev g++ dpkg-dev
Reading package lists... Done
Building dependency tree       
Reading state information... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
 dpkg-dev : Depends: libdpkg-perl (= 1.18.4ubuntu1.5) but it is not going to be installed
 libc6-dev : Depends: libc6 (= 2.23-0ubuntu11) but 2.27-3ubuntu1 is to be installed
             Depends: libc-dev-bin (= 2.23-0ubuntu11) but it is not going to be installed
E: Unable to correct problems, you have held broken packages.


ubuntu@ubuntu:~$ sudo apt install --reinstall build-essential libc6-dev g++ dpkg-dev libdpkg-perl libc-dev-bin
Reading package lists... Done
Building dependency tree       
Reading state information... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
 bind9-host : Depends: libbind9-160 (= 1:9.11.3+dfsg-1ubuntu1.1) but it is not going to be installed
              Depends: libdns1100 (= 1:9.11.3+dfsg-1ubuntu1.1) but it is not going to be installed
              Depends: libisc169 (= 1:9.11.3+dfsg-1ubuntu1.1) but it is not going to be installed
              Depends: libisccfg160 (= 1:9.11.3+dfsg-1ubuntu1.1) but it is not going to be installed
 crda : Depends: libssl1.1 (>= 1.1.0) but it is not going to be installed
 cron : PreDepends: dpkg (>= 1.15.7.2) but it is not going to be installed
        Depends: libpam0g (>= 0.99.7.1) but it is not going to be installed
        Depends: adduser but it is not going to be installed
        Depends: libpam-runtime (>= 1.0.1-11) but it is not going to be installed
 init-system-helpers : Depends: perl-base (>= 5.20.1-3) but it is not going to be installed
 libc-dev-bin : Depends: libc6 (< 2.24) but 2.27-3ubuntu1 is to be installed
                Recommends: manpages-dev but it is not going to be installed
 libc6-dev : Depends: libc6 (= 2.23-0ubuntu11) but 2.27-3ubuntu1 is to be installed
 libdpkg-perl : Depends: dpkg (>= 1.16.3) but it is not going to be installed
                Depends: perl but it is not going to be installed
                Recommends: libfile-fcntllock-perl but it is not going to be installed
 linux-headers-generic : Depends: linux-headers-4.15.0-29-generic but it is not going to be installed
E: Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.

And so on... Running dpkg --get-selections | grep hold does not yeild any held packages. My GCC version: gcc (Ubuntu/Linaro 5.4.0-6ubuntu1~16.04.11) 5.4.0 20160609

Any help with this is greatly appreciated!