It seems that Corona (the iOS 5.0.1 untether), at least, does allow an App Store application to call exec(). I am honestly not certain why that is allowed... I am, however, also not entirely certain whether that is normally disallowed: it might actually not be considered a problem by Apple.
The reason why I point out that there might actually not normally be a restriction against exec() is that I just tested using fork() on my iOS 5.0.1 iPhone 4S using Corona (Absinthe 0.4) and, in fact, you can't call that from an App Store application. (So, the sandbox works. ;P)
The sandbox daemon was then asked by the kernel to verify whether that process was allowed to fork, and as it was not I got the following log message and the process was denied. (I say "denied" as it was not killed: it just got -1 from fork() with EPERM.)
Jun 18 15:00:16 Transponder sandboxd: Facebook(759) deny process-fork
Moving on, your comparison to SELinux is, AFAIK, fairly accurate; on Ubuntu, AppArmor is also a similar system to the Apple sandbox (and, transitively, SELinux). It should be pointed out, however, that these systems are also per-process: I can still install things on the computer and mark them "no limits".
As for your other comments, App Store applications on jailbroken devices still cannot snoop into your keychain, mail, or the data stored for other applications such as Facebook. They do have access to your camera roll, but that is true of non-jailbroken devices as well (this is fixed on iOS 6).
Finally, you are correct in that installing a .deb on your system is handing the packager the equivalent of a temporary root shell on your device: in addition to installing arbitrary code with the package (the point of installing it at all), it gets to actually run scripts as root during the (un)installation itself.
Going back to my comment that started this sub-thread, I guess the point then still stands, "Too bad there's no way to side-load unsigned (or signed by a custom CA) apps while still maintaining the sandbox restrictions." (i.e. no "safe thirdparty appstores") ;)
[quick note on the camera roll thing, I think apps are denied access before the user confirms a location permission popup]
[another quick note on the exec() thing, exec() probably wouldn't work since appstore codesign only works on a single binary. probably related to why only static libraries are allowed, too]
[edit: the fork/exec thing may also be tied in to the strict limitations on background processing for appstore apps? interesting to see your cycript experiment there!]