First of: the energy W does not increase exponentially it increases quadratic!
Second:
What do you want?
Energy density!
So to get good high energy density you need high C because you can (as you already stated) only go to a certain amount of voltage until you get a breakdown. The problem is, C does not change easily. If you take a simple Plate - Plate capacitor
$C \propto \frac{A}{d}$ where A is the Area of the plates and d the distance between them. The smaller the distance the higher the electric field gets between the plates gets relative to Voltage ($|\vec E| \propto \frac{U}{d}$) the faster you get a spark. So the only thing you can actually increase safely is the area. That of course increases the wight/size of you capacitor, reducing the Energy density. This generally applies to all capacitors
Wikipedia does have an excellent article about capacitors:
http://en.wikipedia.org/wiki/Capacitor
Third:
About the capacitance:
A spring is a very good analog to your problem:
A newtonian spring has a certain flexibility, describing the force you have to pull it relative to the expansion of the spring:
$F=k \times x$
Where F is the Force k is the flexibility and x the way. So the capacitance is actually k in this analog. But F is not the Energy W.
$E = \int_0 ^x F(x) dx$
So the more you pull the harder it gets to pull because the force from the spring increases. So to get the energy you can not just calculate $E = F \times x$ but you rather have to integrate the way.
That of course gets you to
$E = \frac{1}{2} k x^2$
Back to the Capacitor:
The more electrons you put in it, the stronger becomes the electric field between the plates of the capacitor. So you have to increase the voltage. The capacitance just tells you how high your voltage has to be (how hard you have to push) to put more electrons on the plate.
In a comment on another answer
If dielectrics tend to diminish the field due to the presence of induced dipole moments, how can field lines propagate more effectively than in vacuum?
This is true if we took an isolated capacitor and then put in the dielectric. i.e. if there was a fixed amount of charges on the plates, then yes the dielectric would thus decrease the electric field between the plates, lower the potential difference between the plates, and therefore increase the capacitance of the capacitor, as I'm sure you are familiar with.
However, if we are holding $Q$ constant then we really should be using the equation $U=\frac12\frac{Q^2}{C}$ which then predicts a decrease in energy as $C$ increases. What is going on? The issue is in what is being held constant. In your book's explanation $V$, and hence $E$ is being held constant. So then when you put in your dielectric more charge ends up on the plates. Loosely speaking, field lines start on positive charges and end on negative charges. Therefore, since we have the same electric field magnitude associated with more charges, we have a larger "field density", and hence a larger energy density.
Note that this is why the book says "for the same field" rather than "for any capacitor". The claim only holds true for comparing capacitors at the same potential difference. I think the given explanation about the dipoles is suspicious though, because the dipoles are present even in the scenario where we hold the charge constant and the energy density decreases. I would say in the constant potential case the additional energy comes from the battery, as more work is done to put more charges across the same potential difference.
Best Answer
How is this going to be done?
One of the functions of a solid dielectric is to keep the plates separated.
Air as with other dielectric is an insulator but if the electric field is to large it "breaks down" and becomes a conductor.
So for a given separation of the plates there are dielectrics which have a larger breakdown field strength and so can have, for a given separation of the plates, a larger potential difference across the plates before breaking down than if air were used.
As the aim in the manufacture of a capacitor is to maximise the capacitance in as small a volume as possible and to have a high maximum working voltage as dielectric is often placed between the plates of a capacitor.
Capacitors with air as the dielectric do exist, for example as variable capacitors and as standard capacitors.