What's the smallest size I can squeeze gcc down to and how would I go about compiling it in such a way?
My take:
#define optimize 0
and then rebuild with dead code stripping. :-) You'd be the first to do this that I know of, so, won't necessarily be easy, but, might be a bit smaller than you'd get otherwise.
Otherwise, around 28MB.