FWIW, I'd be happy with 4, and ecstatic with 8GB - on my x86 arch linux laptop with XFCE, firefox, claws-mail, pidgeon, gimp installed, my system partitions add up to 3.6GB. I won't be putting any user data on my non-replaceable eMMC (apart from maybe my ssh keys if it's set up like the Pandora). The only thing I really miss with SZ on my Pandora occasionally are the man pages.
Speed might be an issue, but I don't tend to reboot my handhelds very often, and that's the main thing where fast media helps IMO.
Edit: A recovery partition is a reaonable idea, but IMO that shouldn't take more than a couple of gigabytes. You don't want it fully featured, and you probably don't even want any networking running on it, unless you're able to update the libs with remote holes in it - but a recovery partition you reflash every time is liable to be corrupted at the same time as the main partition. On balance, I think a separate computer with updated libs is preferable to a recovery partition most of the time. If my arch laptop needs to have its partitions reformatted, I tend to boot off an external CD drive.