To add a little data on my experience last time I tried this, using UPX [0], you can get GTK+ 3 down to 9 MB. Most of the size of Qt comes from ICU, which can be feature selected to decrease its size [1]. With that and UPX, Qt can get down to 16 MB. And those can both be compressed another 30% with ZIP files for shipping.
While those aren't great numbers, I personally think it's tolerable for most usages.