Would it work if I added the NAT gateway to my internet route table instead of the main route table? What’s the difference?
A NAT Gateway is for routing traffic for instances in a private subnet and has its own route table. You have to update the route table of the private subnet hosting the EC2 instances. That route table should be updated to direct Internet-bound traffic to the NAT gateway. For setup details, see: https://aws.amazon.com/premiumsupport/knowledge-center/nat-gateway-vpc-private-subnet/