AWS Services that need a IGW, NAT instance or VPN server to access in VPC

The the following services can NOT be accessed via a private IP address in your VPC. Therefore, they require the use of the AWS Internet Gateway (or NAT instance):

1. EMR : Because access to and from the AWS cloud is a requirement of the cluster, you must connect an Internet gateway to the VPC subnet hosting the cluster. If your application has components you do not want connected to the Internet gateway you can launch those components in other subnets you create within your VPC. In addition, because of the need to access the AWS cloud, you cannot use Network Address Translation (NAT) when you are running Amazon EMR on a VPC.
2. S3 : This is straight forward as S3 is accessed via a URL.  Therefore, the requests hits the IGW and accesses the S3 bucket.  NAT can not be used here.
3. DynamoDB : The AWS API endpoints are external to a VPC and the instance requires an Internet connection in order to reach them. You can either assign an Elastic IP and route the traffic directly out through the Internet Gateway, or use a NAT instance. The latter makes it possible for instances in private subnets to get access to the Internet. These instances will not need any public IP addresses. Instead, they go out to the Internet through a NAT instance in your public subnet.

Requires IGW or VPN server:
4. VPC to VPC : You can use an open source VPN server like OpenVPN (this allows you to not open up your instances by placing them in a public subnet and using elastic IPs).  You could use IGW with elastic IPs attached to the instances.

Traffic costs between EC2 instances, AZs, and VPCs

Often times when running on AWS you will have multiple AZs, accounts and VPCs.  This is a simple summary of EC2 data transfer costs:

1. Within the same AZ  : Free: It is within the same AZ and over private IP.
2. Between two AZs :   Cost. Will incur inter-az charges for both inbound and outbound

3. Between Accounts in different VPCs :  Cost. Inter-az charges are applicable for data transfer charges between instances in the different AZ's (same region) and in different accounts.
4. Between one EC2 classic instance and VPC EC2 instance in a same AZ : Cost
5. Instances to S3 in the same region: Free
6. Instance to S3 in different region: Cost. cross region charges

AWS VPC public and private subnets

What is the difference between a private and public subnet? I asked myself this after I was looking for a field in the ec2-describe-subnets command, AWS console, and ElasticWolf, and could not find anything to indicated whether a subnet was private or public...

Public and private subnets are more or less the same thing.  The routing table will decide whether a subnet is public or private. A subnet with a default route to the Internet Gateway, and instances using Elastic IPs, is considered as public. If you remove the Internet Gateway, you now have a private subnet.
This means that instances in a private subnet are invisible to the outside world and don't have access to the outside world (i.e internet).  Therefore, instances in private subnets need to make use of a NAT instance. The NAT instance will basically accept all traffic coming from the private instances and send it out to the Internet Gateway. That would theoretically add some latency.

Back to my original question: So, if an IGW is associated with your subnet it is a public subnet.