They don't have to install unencrypted programs, but they do have to make the unencrypted versions available to users. Of course, those versions won't be useful to anyone whose device won't run unsigned programs (or won't run A4 executables, etc.). Tivo also has to provide the somewhat-unhelpful binaries with their devices.
(It's a bit different from the Tivo case in that Apple would be fine with not permitting any GPLed code on these devices, whereas Tivo actually ships their devices with GPLed code on them. Apple can just not distribute any code through the App Store that is submitted by someone without the right to grant Apple the rights they need for their process.)