I'm shocked this isn't a feature of a VPC out of the box (shared internet bound traffic). You should only need a NAT gateway if you want the traffic to come out of a single set of external IPs that you control.

Almost all of my use cases I could easily ride out to the internet through a shared pipe (apt updates and such) and don't care whatsoever what IP that exits the AWS network from, since I'm not applying firewall rules or anything.