What is the advantage of using a NAT plus private sub-net on AWS vs a public sub-net with locked down security groups and ACL?

Solution 1:

Many configurations need to share a single public IP. They need NAT. Your scenario's network traffic is all internally initiated. (SQS is polled.) With this type of traffic, there is no advantage to affording a NAT instance.