AWS VPC internet gateway and AWS services

Am I doing something wrong or is the AWS VPC ec2 instances not able to reach any of the AWS managed services (s3/sns/sqs) without a public route to the Internet Gateway in the routetable?

That's correct. If you need to use those services, your instances will need EIPs or public IPs or you'll need a NAT host in your VPC. A VPC is truly private, and it operates in the same manner a well-maintained corporate network does: only allowing traffic that you explicitly allow.

It's worth noting: managed services like RDS, Elasticache, Redshift, etc, can indeed run within your VPC.

AWS has added VPC endpoints for various services, including S3 (2015), EC2 (2017), SNS (2018), and SQS (2018), which lets you use those services without public Internet access.

• New – VPC Endpoint for Amazon S3 (AWS Blog)
• New – AWS PrivateLink for AWS Services: Kinesis, Service Catalog, EC2 Systems Manager, Amazon EC2 APIs, and ELB APIs in your VPC (AWS Blog)
• Amazon Simple Notification Service (SNS) now Supports AWS PrivateLink (What's New with AWS)
• Amazon SQS now Supports Amazon VPC Endpoints using AWS PrivateLink
• AWS VPC User Guide: VPC Endpoints