API Calls from lambda in my VPC to external URL are 2 minutes long

When you say "perform those calls locally" I assume you put an EC2 instance on the same subnets that you have configured for Lambda? If not, that's the test you need to run.

The usual cause here is that the Lambda subnets (plural is important!) do not have the same connectivity as the rest of the VPC. Another common cause is that one Lambda subnet is correct and another is not. So for those subnets, check route tables, NACLs, DHCP and DNS settings.

For a first-call delay like that I'd highly suspect that DNS is an issue. Either the DNS server that the Lambda function is using is not responding correctly so it is falling back to a secondary (although that shouldn't take two minutes); or the endpoint that you're calling is trying to do a reverse DNS lookup on the Lambda IP (public IP - whatever is assigned to NAT Gateway or your NAT device) and it eventually times out and on the next call it has given up. So you might also look at setting a specific reverse IP lookup record.

Are you working in an environment where network appliances inspect traffic routed to the internet? I've seen something similar, though not nearly as long when communicating with internal resources due to the amount of traffic inspection.