Nondeterminism is on average useless for circuits?
1) Realize that nondeterminism is a red herring here. You could have used alternation or circuits that have gates that solve the halting problem. It boils down to a simple counting argument that once you fix the model, you can only compute $2^k$ functions that have a $k$ bit description.

2) For uniform classes like P this is more challenging, as there is no clear definition of "average function in P" and the counting arguments no longer work so cleanly. It's consistent with current knowledge that everything in P can be solved in nondeterministic linear time.