Ok, I've just got it all set up.
I used Audio Queues for the music stream simply because it is the ONE part of the iPhone SDK that is well documented:
http://developer.apple.com/iphone/library/documentation/MusicAudio/Conceptual/AudioQueueProgrammingGuide/AboutAudioQueues/AboutAudioQueues.html#//apple_ref/doc/uid/TP40005343-CH5-SW1
for the general explanation and
http://developer.apple.com/iphone/library/documentation/MusicAudio/Conceptual/AudioQueueProgrammingGuide/AQPlayback/PlayingAudio.html#//apple_ref/doc/uid/TP40005343-CH3-SW1
for a great example (that is a bit buggy)
this seems to work fine along side openAL. and it does seem that it will allow us to jump randomly about the stream at a sample level of accuracy.
the only remaining thing to do is get it so we can load from memory, this is done by replacing the:
AudioFileOpenURL
Call with a call to:
AudioFileOpenWithCallbacks
Unfortunately the documentation for the Audio File Services is... poor... to say the least.
read it at your own risk, and then after it inexplicably doesn't work read:
http://developer.apple.com/iphone/library/qa/qa2009/qa1676.html
where it tells you that the callbacks are actually optional, and by supplying a write one you are telling it to open the file for writing which it can't do for MP4s, so just pass NULL for the write and setSize callback.
I would also like to say that the two answers here recommending MIDI are almost certainly the right way to go if you really want the smallest size.
Unfortunately we are lazy and just wanted something in quickly, it also came to light that we could fit in moderately compressed audio. I was also slightly worried about the performance implication (I don't know what that would be for midi) but apparently this method for compressed audio here uses hardware decoding.
If you want to go the traditional compressed audio route hopefully this helps, you could also try the Audio Converter Services if you want to use the data with openal, unfortunately this API also falls into the embarrassingly poorly documented reference manuals. I don't even know if it works, and if it does, I'm not sure if it uses the hardware decoders.