SQS I believe started in 2004, but in a very limited capacity. I think that MTurk also started in 2004.
Andy Jassy is the one that came up with the vision for AWS. S3 was called S4 at the beginning! There was a big vision on the payments part, but I think S3 + EC2 took off faster than anyone expected, and I credit these two as the main reason why (IMHO) AWS has been so incredibly successful.
I had the privilege to work and interact with Andy Jassy in my past (I was at AWS 2008-2014 and I met him and sat with him numerous times, despite I wasn't based in Seattle), and I can say that I'm pretty sure I've never seen a leader as focused, as effective, as visionary as Andy.
The "2 pizzas team" structure at Amazon and therefore at AWS was also very conducive to running many experiments and failing fast.