For me to make this work, I had to:
Configure the IAM Role used for the connection to include following policies:
Add VPC endpoints for the following services (with the subnet used in the GLUE connection toggled on - find this by creating a errornous connection in Glue, and you can see it there - dno if you can find it other places)
Configure the Amazon Redshift Inbound and Outbound rules according to: https://docs.aws.amazon.com/glue/latest/dg/aws-glue-programming-etl-connect-redshift-home.html - the Set up Amazon VPC section.
Since I've played around with this for almost the entire day, I might have toggled other stuff too, but at least I needed these settings :)
And for the life of me, I don't get why permissions in cloud providers have to be this complicated - I get they need to stay secure, but I have probably today introduced multiple vulnerabilities in my cloud setup, just playing around with stuff I had no clue about what actually did, just trying to get this connection to work.