Sorry to waste your time, corrupted files caused the problem! All working fine now.
So, I just installed Magento CE 2.1.5 on my root (Ubuntu 16.04 - installed apache, php7, php extensions, mysql and all that stuff from the repositories).
I checked the requirements and there should be no problem there (at least that I can see). During the installation there were no errors.
This is what I am getting: http://542.s.hostens.cloud (just click any link)
I suspected some problem with mod_rewrite/htacess.
Find phpinfo(); here: http://542.s.hostens.cloud/derp.php
Any ideas what might be causing this behavior? (I stuck to the guides Magento guides for htacess and mod_rewrite.)