Shockingly, and unbelievably I got this working finally. I've logged over 100 minutes in Steam just for the splash screens starting up.
I've tried a huge amount of things, but this was the final thing that actually worked.
Steam won't start on ubuntu GNOME 16.04 - Ask Ubuntu
Basically these lines:
mv ~/.local/share/Steam/ubuntu12_32/steam-runtime/i386/lib/i386-linux-gnu/libgcc_s.so.1{,.disable}
mv ~/.local/share/Steam/ubuntu12_32/steam-runtime/i386/usr/lib/i386-linux-gnu/libstdc++.so.6{,.disable}
mv ~/.local/share/Steam/ubuntu12_32/steam-runtime/amd64/lib/x86_64-linux-gnu/libpcre.so.3{,.disable}
mv ~/.local/share/Steam/ubuntu12_32/steam-runtime/amd64/lib/x86_64-linux-gnu/libpcre.so.3.12.1{,.disable}
I hope it works for others but I wouldn't be surprised if it didn't...