quite. You can get a debian-based distro down to about 56MB uncompressed: http://www.emdebian.org/grip/index.html (using the grip bloat-removal tools), or 90Mb without (corresponds to 'nano').
To go smaller you need to scrap the upgradable-in-place aspect.
Generally, embedded system uses NAND and JFFS2 and it can provide ~50% compression ratio which makes 90MB to be ~45MB (or 56MB to be ~28MB). These are already small.
For system not using NAND but eMMC for example, a few hundred MiB is not a big deal.
In both cases, leaving pkg system in rootfs may be a better idea for its benefits.
Regards, JD