Here is a partial answer to the question of how many cuts it takes before the nonempty pieces are singletons with high probability when the hyperplanes are chosen uniformly. Consider the roughly $4^n$ pairs of vertices of the cube. Each pair is separated by a hyperplane iff the partition separates all vertices. The expected number of pairs which intersect no hyperplane is at most $4^n$ times the probability that a particular edge is missed, since adjacent vertices are the least likely to be separated. The probability that none of the $k$ hyperplanes intersects an edge is $p^k$, where $p$ is the probability that each hyperplane misses the edge.
What does it take for a hyperplane to separate two adjacent vertices? These points determine a great circle, and are at angle $\arccos \frac{n-2}{n} \approx \frac{2}{\sqrt n}$. The hyperplane almost surely intersects this circle in two antipodal points. If these intersect the arc of about $\frac{2}{\sqrt n}$ radians, then the hyperplane intersects the edge. So, the probability that a random hyperplane intersects an edge is about $\frac{2}{\pi\sqrt n}$. The probability the edge is missed is the complement, about $1- \frac{2}{\pi\sqrt n}$. The probability all $k$ hyperplanes miss this edge is about $(1- \frac{2}{\pi\sqrt n})^k \approx \exp(-\frac{2k}{\pi\sqrt n})$. The expected number of pairs not separated by any hyperplane is at most about $4^n \exp(-\frac{2k}{\pi\sqrt n})$.
If you choose $k\approx c n^{3/2} \log n$ n^{3/2}$then the expected number of pairs not separated by any hyperplane is at most$1$. For much larger$k$the expected number of pairs of vertices in the same part, hence the probability that two vertices are in the same part, becomes small. Post Undeleted by Douglas Zare 2 Now separating all pairs of vertices instead of just pairs of adjacent vertices.; deleted 13 characters in body I corrected an earlier version which assumed that only adjacent vertices need to be separated to guarantee the parts are singletons, which fedja pointed out was incorrect. Thanks. Here is a partial answer to the question of how many cuts it takes before the nonempty pieces are singletons with high probability when the hyperplanes are chosen uniformly. Consider the roughly$n2^{n-1}$edges 4^n$ pairs of vertices of the cube. Each edge intersects pair is separated by a hyperplane iff the partition separates all vertices. The expected number of edges pairs which intersect no hyperplane is at most $n2^{n-1}$ 4^n$times the probability that a particular edge is missed, which since adjacent vertices are the least likely to be separated. The probability that none of the$k$hyperplanes intersects an edge is$p^k$, where$p$is the probability that each hyperplane misses an edge, and$k$is the number of hyperplanesedge. What does it take for a hyperplane to separate two adjacent vertices,$v$and$w$? ? These points determine a great circle, and are at angle$\arccos \frac{n-2}{n} \approx \frac{2}{\sqrt n}$. The hyperplane almost surely intersects this circle in two antipodal points. If these intersect the arc of about$\frac{2}{\sqrt n}$radians, then the hyperplane intersects the edge. So, the probability that a random hyperplane intersects an edge is about$\frac{2}{\pi\sqrt n}$. The probability the edge is missed is the complement, about$1- \frac{2}{\pi\sqrt n}$. The probability all$k$hyperplanes miss this edge is about$(1- \frac{2}{\pi\sqrt n})^k \approx \exp(-\frac{2k}{\pi\sqrt n})$. The expected number of edges missed pairs not separated by all hyperplanes any hyperplane is at most about$n2^{n-1} 4^n \exp(-\frac{2k}{\pi\sqrt n})$. If you choose$k\approx c n^{3/2} \log n$then the expected number of edges missed pairs not separated by all hyperplanes any hyperplane is at most$1$. For much larger$k\$ the expected number of edges missedpairs of vertices in the same part, and hence the probability that at least one edge is missed two vertices are in the same part, becomes small.