4G is a bit over the top. My install (TeXLive 2010 on OpenBSD) is ~2G, and that includes gobs of rarely-used packages and documentation.
Really, borrowing MikTeX's install-on-first-use for packages and making documentation optional should result in a much more reasonable size. If you want to get fancy, teach LaTeX how to decompress packages on demand.
Here comes the problem: Apple requires it to be a single binary, distributed once. You can't install packages the LaTeX ways should you want to, so you have to bundle most (if not all) packages into the single binary.
You could use a virtual machine library (if anything suitable exists) and run everything inside one executable - it would probably have horrid performance but you get rid of the single binary restriction. You can put on a nice front-end and tell the user how much longer he has to wait until the operation is complete.
Virtual machines are generally prohibited by the guidelines as well. (Exceptions exist for things like script interpreters, which need to be present for some games to run, e.g. Lua.)
I think the difference here is between interpreting scripts that come with the binary, and downloading new scripts from the internet (or other untrusted locations). The latter is prohibited.
To get around it, you'd have to make it In App Purchases, because these also come from a the App Store.
Apple wants to restrict the platform options available to preserve their user lock-in. They were sort of forced to make an exception for games because they had no alternative to offer.
It seems the cult of Apple is touchy today and can't detect a joke. I'm sorry if I have inadvertently hurt your feelings - I will be sure to clearly state my humorous intentions next time. </humour>
For the record, I do not own devices based on iOS or Android and I don't care for your little Apple-Google feud with which you seem to be so concerned with. So please, carry on with those market statistics about Android, I am dying to know more.
Really, borrowing MikTeX's install-on-first-use for packages and making documentation optional should result in a much more reasonable size. If you want to get fancy, teach LaTeX how to decompress packages on demand.