Neural Network Golf: smallest network for a certain level of performance
You might be interested in this paper that explores a few of the questions you are asking: http://arxiv.org/pdf/1312.6184.pdf. It is aptly titled: "Do Deep Networks Really Need to Be Deep?"

The crux of the matter is that deep networks allow for a LOT of non-linearity in the data that is being described. For CIFAR-10, I suspect that something similar to what works well for MNIST will work well. Yan LeCunn's page about MNIST results gives a lot of clues about models with few parameters: http://yann.lecun.com/exdb/mnist/

The double-problem of image classification is that in addition to the classification you need to extract features somehow. Often the parameters in deep networks go towards feature extraction rather than the classification itself, which is usually a softmax multi-class logistic regression classifier.