The story I always heard was they had a ton of extra capacity that was very seasonal and then someone came up with the great idea to sell that extra capacity in the off season.

SQS as the first publicly available service sounds weird to me but I don't have any sources to cite otherwise.

Edit: Wikipedia says SQS was the first service https://en.wikipedia.org/wiki/Amazon_Web_Services#History