Example demonstrating the power of non-deterministic circuits
If this problem has no progress, I have an answer.

--

I also have considered this problem since my COCOON'15 paper (before your question).

Now, I have a proof strategy, and it immediately gives the following theorem:
There is a Boolean function $f$ such that the nondeterministic $U_2$-circuit complexity of $f$
is at most $2n + o(n)$ and the deterministic $U_2$-circuit complexity of $f$ is $3n - o(n)$.

I apologize that I haven't written the paper.
The proof sketch below might be enough to explain my proof strategy.
I aim to write the paper with more results by the STACS deadline (Oct. 1).

[Proof Sketch]

Let $f = \lor_{i=0}^{\sqrt{n}-1}{Parity_{\sqrt{n}}(x_{\sqrt{n} \cdot i + 1}, \ldots, x_{\sqrt{n} \cdot i + \sqrt{n}}})$.

The deterministic lower bound proof is based on a standard gate elimination method with a little modification.

The nondeterministic upper bound proof is a construction of such nondeterministic circuit.


Construct a circuit computing $Parity_{\sqrt{n}}$. (The number of gates is $o(n)$.)
Construct a circuit selecting $\sqrt{n}$ inputs nondeterministically. (The number of gates is $2n + o(n)$.)
Combine the two circuits.