Consider the length-2 n-cube with vertices $(\pm 1,\pm 1,\cdots ,\pm 1)$, which we will apply some rotation to.
Let $V = \{(a_1, a_2, \cdots, a_n), (b_1, \cdots, b_n), \cdots\}$ be the set of vertices in the rotated hypercube. I am looking for $\min(\max(\{|x_1|, \cdots, |x_n|\}) : x \in V)$. Since $\max(\{|x_1|, \cdots, |x_n|\})$ is equivalent to the size of the (origin-centered, axis-aligned) hypercube which touches vertex $x$, the overall goal is to find the minimum-size hypercube which touches at least one vertex in $V$.
Another way of looking at it is that if you place an axis-aligned bounding box around $V$, the goal is to find the smallest dimension-component of the box.
By symmetry, it's apparent that there will be an even number of vertices with this minimum, and the resulting value is obviously $\ge 1$. But despite it seeming like this should be a value that you can compute directly from the rotation matrix, I haven't found a simple solution yet.
For my particular problem, there is additional structure: $n=64$ and the rotation is that of the 2D 8x8 DCT used by JPEG.