Since I decided to incorporate FBConnect in my game, I'm now using Iphone OS 2.2 again. Why? Well, as it turns out, FBConnect doesn't run properly on iPhone OS 3.0. So, I had to choose between iPhone OS 3.1 or somehow solve the size issue and go to iPhone OS 2.2.
So, which would it be? Well, iPhone OS 3.1 was pretty much out of the question. 3.0 was kinda of okay. I was not happy about it, but I thought it would be fine. 3.1 however, that would seriously limit the user base.
So instead I decided I'd solve this. How did I do that? I decided to go with wav's. Gzipped wavs. That way I managed to get the app to a size of about 8 MBs (for the .app). And I think (but I'm not quite sure) that the file that will be in the app store will be even smaller, since the file you upload to Apple is compressed. That file is 6 MB. So it's all good. :)
You can see my gzip implementation here (scroll down a little bit):
http://stackoverflow.com/questions/1588861/zlib-iphone-files-get-crap-in-beginning
Also, the issue I was having with crackling sound went away with the usage of wavs.
:D