Alright, so I found my biggest problem. It's rather stupid.
I was missing the services configuration...
<endpoint address="" binding="wsHttpBinding" contract="MyProject.IMyService" bindingconfiguration="BasicAuthentication"></endpoint>
I remember that used to be generated in earlier versions of WCF.
Anyway, with that in place I was able to fix it.
Having Basic Authentication without HTTPS is impossible, but I was able to get it working by just ignoring the certificates in my code:
using (ServiceApiClient client = new ServiceApiClient())
ServicePointManager.ServerCertificateValidationCallback += new RemoteCertificateValidationCallback((sender, cert, chain, error) => true);
client.ClientCredentials.ServiceCertificate.Authentication.CertificateValidationMode = X509CertificateValidationMode.None;