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 $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$ 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.

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 $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}$ 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.

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 $n2^{n-1}$ edges of the cube. Each edge intersects a hyperplane iff the partition separates all vertices. The expected number of edges which intersect no hyperplane is $n2^{n-1}$ times the probability that a particular edge is missed, which is $p^k$, where $p$ is the probability that each hyperplane misses an edge, and $k$ is the number of hyperplanes.

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 by all hyperplanes is about $n2^{n-1} \exp(-\frac{2k}{\pi\sqrt n})$.

If you choose $k\approx c n^{3/2} \log n$ then the expected number of edges missed by all hyperplanes is $1$. For much larger $k$ the expected number of edges missed, and hence the probability that at least one edge is missed becomes small.

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 $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$ 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.