The fact that the class of NN functions is universal is almost vacuous: the basic idea is that if you allow a "neuron" for every point in your input space then you can mimic any function you like (i.e. each neuron handles a single input). Obviously such representations become arbitrarily large.

Which almost immediately suggests a solution to why NN learning works: the processes that produce the types of datasets humans are interested in are produced by (effectively) polysized networks and you can probably say things like the probability of recovering a polysize function from polysize samples is high.