Algorithm to compute decomposition of a union of sets to a disjoint union of intersections
No, not $O(n)$.  Suppose $0.9n$ are nested and $0.1n$ are not nested (and are unrelated).  Then there can be at least $2^{0.1n}$ different pieces, which is not $O(n)$.

You can find the nesting structure in $O(n^2)$ time by testing all pairs of sets to see which are subsets of the other.