Thesedays, 23MB for mobile game sounds not that big at all. Unity has many great advantages, but it's shared libraries, mono files and so on takes a lot of place unfortunately.
The other way round, Apple has limited their apps to be downloaded over 3G to 100MB, so the 23MB is not that much anyway, in comparison to this limit. Especially, that now the size won't be increasing very rapidly.
A lot of not very big apps was made with Unity and I suppose that users aren't expecting the apps to be very small. You can take a look at Unity's Showcase and filter it by iOS/Android platform, then check the app size in the store - they're about 40MB for simple 2D game, so it's not that unusual.
Unity development is just mush more faster than native, or even cross platform development like Adobe AIR, and you have all platforms you need. Also the performance is almost as good as native, especially for smaller teams without extra time and money to tweak their own, specialised engines.
EDIT: With other C++/C# executables it is often common, that these installers doesn't include shared Redistributable packages, which add few MB to the overall build size if they were included. Here Unity is including everything. Also being managed, not native language seems to add some overhead.
Also the overhead according to the Unity documentation, could be reduced from 23MB to 12MB:
How small can an app be made with Unity?
An empty project would take less than 22 MB in the App Store if all the size optimizations were turned off. If you own an Advanced License (and therefore have access to the stripping option), the empty scene with just the main camera can be reduced to less than 12 MB in the App Store (zipped and DRM attached).
Here's the guide to decreasing this size: build size optimization.