What would be nice if in the app stores they showed how much space your app would you and let you sort on that, give some sort of incentive to reduce your size.
One of the advices of Google IO this year was to try to keep applications small.
According to Google bigger applications are the ones that get deleted first when space gets short. Most of the time are never reinstalled.
Regarding APK size, you can do miracles by using ProGuard (even with obfuscation disabled), though it will obviously fail for native code, like in the Qt case.
Day job is actually JVM/.NET/C++ enterprise applications.
Nonetheless, even my device is not swimming on free space, so I do have some care with it. And given my age, I am used to the time when every byte counted.
On my hobby development I tend to do a mix of Java/C++, depending how portable I want to do it.
When you build a Qt app statically you can strip all the unused functions out. But doing it for loading by the Android NDK? That seems a little trickier. You'd need to rebuild the libs specifically for that application.
Maybe there will be a better solution in the future to handle this, but it also seems likely that the native side wouldn't grow much past this size (i.e. 1 line of "hello world" is 26MB but 100,000 lines of real application code would only grow to 28MB.)
However, the Android demo apps are 16MB and 23MB in size, respectively. For the larger one (Introduction to Qt5) the uncompressed sizes are: 9MB of data, 26MB native code, 134KB of dalvik code.
This looks like a major burden for low-end devices, even though I must admit the demo is looking great (and performs rather fluently on my HTC Vision, running Android 4.2.2).