$\newcommand{\E}{\mathbb{E}}$For the first question, we cannot hope in the full generality for the $\Omega(N^2 \log (1/\varepsilon))$ lower bound --- say, if we look at a symmetric matrix $W$ with independent $\{\pm 1\}$ entries, we can encode the matrix $U$ exactly just by specifying matrix $W$ explicitly, which we can do using $N^2$ bits.
The lower bound $\Omega(N^2)$ for constant $\varepsilon=0.01$ is conceptually simple, let me discuss only the case where $W$ is a $\{ \pm 1\}^{n \times n}$ (symmetric) matrix, and then briefly discuss how to generalize it, to -- say, any symmetric distribution of entries $W_{ij} \sim - W_{ij}$ with variance one $\E W_{ij}^2 = 1$ and bounded fourth moment $\E W_{ij}^4 \leq B$.
We will use the following
Lemma
Let $f: \{ \pm 1\}^n \to \{0, 1\}^m$ be an encoding function, and $g:\{0, 1\}^m \to \{\pm 1\}^n$ be decoding, s.t. with probability at least $1/3$ over random $x \in \{ \pm 1\}^n$ we have $d_H(g(f(x)), x) \leq 1/4$, where $d_H$ is the normalised Hamming distance $d_H(x, y) := |\{k : x_k \not= y_k\}|/n$. Then $m \geq n/2$.
This is very standard, see for example Lemma 2 in
Entropy arguments used by Jean Bourgain.
Clearly this implies the following
Corollary
Let $f : \{ \pm 1\}^{n\times n} \to \{0, 1\}^m$ be an arbitrary encoding, and $d: \{0, 1\}^m \to \{ \pm 1\}^{n\times n}$ be a decoding, and $W$ be a symmetric Wigner matrix with independent $\{ \pm 1\}$ entries (above diagonal). If $\|d(f(W)) - W \|_F \leq 2^{-4} n^2$ with probability at least $1/3$, then $m\geq n^2/4$.
This is just because on $\{\pm 1\}^{n \times n}$ the Hamming distance between corresponding vectors is (up to a constant factor) the same as Froebenius norm of the difference between the matrices.
I will show that if we could encode the matrix $U$ up to a small Frobenius norm error $2^{-12} n$ with $n^2/16$ bits, then we could encode matrix $W$ up to a small Frobenius norm error with $n^2/4$ bits --- which by the previous corollary is impossible.
We will encode $W$ as a pair $(\tilde{U}, \tilde{D})$. Since with high probability all eigenvalues of $W$ are in the range $\pm O(\sqrt{n})$, by simple discretization we can encode the vector of eigenvalues up to an element-wise error $n^{-10}$ using $O(n \log n)$ bits --- ensuring that $\|\tilde{D} - D\|_F \leq 1$.
If we could find orthogonal $\tilde{U}$ s.t. with probability $1/3$ we had $\|\tilde{U} - U\|_F \leq 2^{-12} n$, and encode $\tilde{U}$ using $n^2/16$ bits, we would chose $\tilde{W}$ to be the Frobenius-norm projection of $\tilde{U} \tilde{D} \tilde{U}^T$ on symmetric $\{\pm 1\}^{n\times n}$ matrices.
We will argue that $\|\tilde{W} - W\|_F \leq 2^{-4} n^2$. Indeed, if $\|\tilde{U} - U\|_F \leq 2^{-12} n$ since $\|D\|_F \leq O(n)$, we get
$$
\|\tilde{U} D \tilde{U}^T - U D U^T\|_F \leq \|U D (\tilde{U}^T - U^T)\|_F + \|(\tilde{U} - U) D \tilde{U}^T\|_F \leq 2 \|(\tilde{U} - U) D\|_F \leq 2^{-6} n^2,
$$
Similarly if $\|D - \tilde{D}\|_F \leq 1$ then
$$
\|\tilde{U} D \tilde{U}^T - \tilde{U} \tilde{D} \tilde{U}^T\|_F = \|D - \tilde{D}\|_F \leq 1,
$$
hence by triangle inequality we have
$$
\|W - \tilde{U} \tilde{D} \tilde{U}^T\|_F \leq 2^{-5} n^2.
$$
Let us now take $\tilde{W}$ to be the projection of $\tilde{U} \tilde{D} \tilde{U}^T$ on symmetric $\{\pm 1\}^{n\times n}$ matrices, i.e. $\tilde{W} := \mathrm{argmin}_{X\in \mathcal{S}} \|X - \tilde{U} \tilde{D}\tilde{U}^T\|_F$ where $\mathcal{S} \subset \{\pm 1\}^{n \times n}$ is the family of all symmetric matrices.
Then by the definition of projection, and since $W$ itself in $\mathcal{S}$ matrix we have $\|\tilde{W} - \tilde{U}\tilde{D}\tilde{U}^T\|_F \leq \|W - \tilde{U}\tilde{D}\tilde{U}^T\|_F$, and by triangle inequality
$$
\|W - \tilde{W}\|_F \leq \|W - \tilde{U} \tilde{D}\tilde{U}^T\|_F + \|\tilde{W} - \tilde{U} \tilde{D}\tilde{U}^T\|_F \leq 2^{-4} n^2.
$$
Since the total encoding of $(\tilde{U}, \tilde{D})$ needs to use $n^2/4$ bits by Corollary, and we can encode $\tilde{D}$ using $O(n \log n)$ bits, the total encoding of $\tilde{U}$ needs at least $n^2/8$ bits.
To handle the case of more general symmetric distribution of entries $W_{ij}$, note that the distribution of $W_{ij}$ is the same as $|W_{ij}| \varepsilon_{ij}$ where $\varepsilon_{ij}$ are independent $\{\pm 1\}$. By the Payley-Zygmunt inequality, with good probability a constant fraction of entries is bounded away from zero $|W_{ij}| \geq \delta$, for some constant $\delta$, and if we recover $W$ with small Frobenius norm error, we will be able to recover the signs $\varepsilon_{ij}$ on a constant fraction of those entries which are bounded away from zero -- and to do this, we need encoding of size $\Omega(n^2)$.
It looks like that the second impossibility is the consequence of the first: if I could write $U=S_1 S_2 \ldots S_m$ for some sequence of $m$ simple unitary matrices $S_i$, we could approximate each $S_i$ by a $\tilde{S}_i$ up to small $\varepsilon \leq 2^{-10} / m$ Frobenius error, s.t. each of the matrices $\tilde{S}_i$ is described using only $O(\log(nm))$ bits. Then $\|U - \prod_i \tilde{S}_i\|_F \leq m \varepsilon \leq 2^{-10}$, and the total number of bits used to encode $U$ is $m \log(nm)$ --- implying $m \gtrsim n^2/\log n$ by the previous discussion.
