No discussion of bloat is complete with a mention of the demoscene, where sub-MB applications generate immensely complex graphics:

https://news.ycombinator.com/item?id=11848097

https://news.ycombinator.com/item?id=3843427

https://en.wikipedia.org/wiki/.kkrieger

(I'm aware that these sizes do not include the OS and its libraries, but apps on a mobile device also have a similarly rich environment of libraries they can use.)