Olhei para o meu histórico de terminal e foi o que fiz antes de fazer o post:
sudo apt-get remove --purge steam-launcher
Eu reiniciei o computador e baixei uma nova cópia do instalador .deb para o Steam do link
Após a instalação, ele passou pelo mesmo processo e não encontrou e instalou esses pacotes. Desta vez, no entanto, a janela de login do Steam apareceu (após uma longa atualização) e eu consegui fazer o login.
Atualmente estou baixando um jogo agora para testar mais. Espero que esta solução ajude.
Update: Eu ainda recebo o erro toda vez que eu inicio o Steam, mas o Steam ainda funciona toda vez. Eu baixei e joguei o Borderlands 2 com sucesso.