So I installed the libs until it stopped complaining. Now it displays this:
WebCore config: library(CENSORED/SteamLinux/SteamApps/common/TalesMajEyal/lib/libte4-web.so) spawn(CENSORED/SteamLinux/SteamApps/common/TalesMajEyal/cef3spawn32)
Loading WebCore: loaded!
[CPU] Detected 4 CPUs
And hangs. The log file is zero size.
Since it's not complaining about any library, I was a bit stuck, but really wanted to play. So I downloaded the steamless version from the website, and it just works.

So I can play, for now, which is great. I am running Manjaro Linux. There were no updates since yesterday other than flashplayer. Since I changed nothing in my system and it affects Steam I got a feeling you'll hear more of this.