Run, it's a mega-commit! I'm sure you've heard of this before, but let's keep to doing formatting/refactoring and functional changes separately. It's very hard to pinpoint the actual functional changes from the essentially one commit making up this branch, because most of the changes look like just moving code around, but sometimes the code added is actually different from the at first sight equivalent code removed from the original location. In general, commits with bullet-point lists (other than motivation / future plans) or "and" in the commit name are almost always bad. However, cross-checking the commitdiff and blobs for the current and the earlier version gives me:

A general observation: I would've preferred if you extended ReadinessHelper sufficiently (just the force status hack probably?) and handled the getall-or-fallback introspection internally without the need to add a separate introspection queue in Connection again. This could be done I think by:
 - having five non-public introspectables which Core depends on
   * IntrospectableStatus
     - calls GetAll, if it returns all of the new properties, sets ready on these first three
     - if not, just sets ready on itself
     - still needs the force status hack, though
   * IntrospectableSelfHandle
     - depends on Status
     - always sets ready on just itself
   * IntrospectableInterfaces
     - depends on Status
   * IntrospectableCapabilities, CAI
     - deps on status, but is always introspected by itself
 - having the Core introspectable just do nothing and set itself to ready (the actual work having been done by its dependencies)
   * maybe having a NULL introspectfunc would be cleanest to make ReadinessHelper just set a feature ready if its dependencies are satisfied (analogous to a "virtual package")
The dependency on status means everything is always introspected only when we know what status we're introspecting them for (eg. SimplePresence can gain new statuses when the Connection goes Connected), and the restart-or-not logic when getting the status initially (and afterwards in StatusChanged signals) will do the right thing.

However, as you've already implemented the more convoluted private introspection queue in Connection and our (supposedly?) extensive enough regression tests haven't barked at it (right?), it's up to you to judge whether it would be beneficial to try and pursue this - my above plan potentially  being just naive thinking overlooking some crucial obstacle, of course. I believe it would enhance Connection maintainability though, the connection introspection logic becoming very complex due to handling optional features and maybe-present interfaces being the reason I proposed the ReadinessHelper mechanism in the first place.

I see C::P::introspectMain has turned into something of a deferred constructor in addition to firing the introspection calls. Why? Can't the connection caps and the ContactManager be constructed in the Connection(::Private) constructor already? (introspectMain() currently is the only place where anything is assigned to these vars). Some parts of C::P() is already split to a init() function in a rather arbitrary way, while you're reorganizing this it might make sense to make C::P() actually be a function just calling a set of smaller (but logical) functions:
 - addIntrospectables()
 - setupHandleContext()
 - construct contact manager, caps
 - connectToSignals()
 - becomeReady()

The word-wrapping causes at least the line 1117 debug string to become "...Ignoringredundant..." (might be other similar issues).

So, nothing wrong on the conformity / bugs side I can spot. As always, feel free to disagree on the implementation sanity / refactoring suggestions :)

Branch merged to master with some trivial enhancements (reviewed by andre). Will be in 0.3.8.