First of all, the human brain is distinctively larger than that of any other primate, mainly due to the great expansion of the cerebral cortex. The underlying structures have remained relatively stable (Toro et al., 2008). As the cortex overlies the rest of the brain, a solution had to be found, because the whole brain did not have to inflate to increase intelligence in men, just the cortex. The answer by @Josh touches on the solution, as folding the cortex increases the surface-to-volume ratio such that an expanding cortical surface fits onto a relatively stable base.
However, the question basically, and very rightfully states: "why not increase volume in order to fit those extra neurons in?". Since the volume of a ball increases by a third power with radius, why on earth would nature keep holding onto increasing the surface area, and not simply inflate the cortex by enhancing its thickness?
This has to do with the fact that the vertical architecture of the cortex has remained remarkably stable during evolution. In other words, evolution of a bigger cortical area to enhance higher cognitive processes has occurred in the most parsimonious way so typical for evolution: take an existing structure and enlarge it when there is need for more.
The cortex typically consists of a thin sheet covering the brain, and is not more than 3 mm thick. The neocortex represents the great majority of the cerebral cortex. It has six layers and contains between 10 and 14 billion neurons. The six layers of this part of the cortex are numbered with Roman numerals from superficial to deep. Layer I is the molecular layer, which contains very few neurons; layer II the external granular layer; layer III the external pyramidal layer; layer IV the internal granular layer; layer V the internal pyramidal layer; and layer VI the multiform, or fusiform layer (Review of Clinical and Functional neuroscience, chapter 11).
Basically, layer IV receives most input from the periphery via the thalamus (visual, auditory, tactile inputs etc.), layer II/III take care of horizontal projections for further processing, while layer V takes care of the output (motor output etc.). This basic architecture cannot be changed easily without changing the entire core workings of the cortex. As an analogy - to speed up computers in a parsimonious way, one can expand the number of processors quite easily. Coming up with a speedier processor is difficult these days, as evolution of single processor capabilities is pretty much at a dead end.
Hence, to increase the number of cortical neurons, the cortical surface must be enlarged. As the basis (subcortical structures) remain pretty much the same, creating folds (gyri and sulci) is the best way, and perhaps the only way to increase cortical surface area.
And to answer the last subquestion - no, neurons do not only exist near surfaces, it is the fact that the cortex is the outer shell of the brain and to expand it, this surface had to increase in size.
- Toro et al., Cerebral Cortex (2008); 18(10): 2352–7