This is more a solution post, as I could find a post similar to my problem and figured a very easy solution.
I set up a mattermost omnibus instance (but I assume this would be valid for any instance) without SSL/TLS. It worked perfectly via browser, but I could not connect with any app (desktop or mobile). What fixed the problem for me was allowing port 80/443 even though mattermost only runs on port 8065. Maybe the apps send some additional requests before connecting.