What is the downside of NOT running AWS Lambda functions in a VPC?

If you need access to resources within a VPC, then run your AWS Lambda function within a VPC. If you do not require this access, then do not run it within a VPC.

If you require Internet access, then you should connect your Lambda functions to a Private Subnet and use a NAT Gateway, which is a fully-managed NAT so you can remain serverless. It will solve the problems you listed.

AWS has provided a reference document for Lambda deployments: Serverless Application Lens, AWS Well-Architected Framework. In it they provide the following decision tree:

The only major downside noted is that a Lambda outside of a VPC cannot directly access private resources within a VPC.