AWS: little more setup, but you can get pretty good performance by hosting the files on S3 and putting CloudFront in-front to replicate world-wide for speed & ultimate uptime. Doing this costs very little as you pay for storage and bandwidth at a very affordable rate (unless you’re hosting large media files such as screencasts / podcasts)
https://github.com/fredjean/middleman-s3_sync and https://github.com/andrusha/middleman-cloudfront are your friends here.
Github Pages: fairly straight-forward deployment with the https://github.com/neo/middleman-gh-pages gem.
A shared host: probably as much setup work as AWS, but you’re pretty much guaranteed to have less uptime and worse performance. That said, there would be nothing to stop you from fronting it with CloudFront or another CDN to mitigate this. The only time I’d recommend is if you’re hosting very large files and want a fixed rate for bandwidth, in which case I’d opt for a VPS from the likes of Linode.
Pairing any of these with a CI service like Codeship is an excellent setup as it takes the load off your machine for building the full site.
Personally, my recommendation is S3, CloudFront and Codeship. I’m looking to move to SauceLabs as my CI so I can run automated cross-browser JavaScript testing during the build process.