Around 15 MB sounds to be the smallest executable size with Delphi for iOS (in Release mode with no debug info). You can try to disable the RTTI generation, if you do not need it. But not with a lot of hope.
It is much bigger than ObjectiveC "native", but it embeds the whole Delphi RTL and the FireMonkey libraries to do all the rendering, therefore it is bigger.
A "plain Objective Pascal" executable using native iOS controls, compiled with FPC, should be smaller. Or when compiled with "Oxygene for Cocoa", it should be much smaller.
But do not look only at executable size, think at the memory used during execution, and general speed. You may have to compare with HTML5 apps embedded with PhoneGap. FireMonkey may be slower at rendering on screen, but native code with ARC memory handling should be more powerful than JavaScript.
Do not forget that your smartphone has now a lot of memory. ;)
Sadly, it is not possible to share some code with external libraries (.so) under iOS, so you won't be able to use something like Delphi packages to reduce the executable size.
Of course, Apple has always done everything in its power to force developers to use its own tools and language. As does Microsoft, especially for Windows 8. Delphi for iOS does not claim to be better than XCode + Objective C, but to be cross platform so that you can share as much code as possible with your server or Windows / Mac OSX apps: you can not use your Objective C code outside the Mac world... but you can share your Delphi code among platforms, even if the UI has to be rewritten for mobiles. This is why a more fair comparison would be with JavaScript/PhoneGap, MonoDroid/MonoTouch or AppCelerator.
Some data, retrieved from StackOverflow:
One concern: AFAIK the size limit for 3G download in the AppStore is about 20 MB.