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 most capacitors (including the simple parallel plate capacitor, which is the one you refer to), changing the applied voltage simply results in more charge being accumulated on the capacitor plates, and has no effect on the capacitance.
A capacitor is nothing more than two conductors which are separated from each other by a dielectric material of some kind. When a voltage is applied across a capacitor, a certain amount of charge builds up on the two conductors. The amount of charge which accumulates is a function of the voltage applied - $Q=Q(V)$. The capacitance is then defined by $C = \frac{Q}{V}$.
Under most conditions, the capacitance ends up being purely a function of geometry. In the case of the parallel plate capacitor, one finds that
$$ Q(V) = \frac{\epsilon_0 A V}{d}$$
so
$$ C \equiv \frac{Q}{V} = \frac{\epsilon_0 A}{d}$$
The capacitance therefore depends on the area of the plates and the distance between them - nothing else.
It's worth noting that one could construct a device which has a more complicated, voltage-dependent capacitance. For example, one could consider a parallel plate capacitor where the plates are held apart by electrically insulated springs. In that case, the distance separating the plates would depend on the electrostatic attraction between the plates, which is determined by the applied voltage. Increasing the voltage would result in a larger charge buildup, which would cause greater attraction between the plates, which would further compress the springs, which would increase the capacitance. Working this out explicitly is an interesting exercise.
But again, for a simple case like the one under consideration in your example, the capacitance is merely a geometrical constant.
Best Answer
The capacitance is the ratio of charge on the plates over the voltage applied. $$C = \frac{Q}{V} \Leftrightarrow Q = C \cdot V$$ The calculation you show determines the capacitance from measured voltage and charge on the plates. You basically know the result you want and determine the size of the capacitor you need.
A larger capacitor, with a larger capacity, will hold a bigger charge at the same voltage. Doubling the area will double the capacitance (in case of a plate capacitor), so for 4 farads of capacity you get $$Q = C \cdot V = 4 F \cdot 5 V = 20 C$$
The pysics works as follows: The voltage is a driving force, pushing electrons through the wires an onto the plates of the capacitor (or sucking them off on the positive pole), until the mutual repulsion of the electrons leads to a balance of foces. If you have a larger plate, the charge can distribute over a larger area, there is less "pileup" and therefore a smaller "pushback force". This is why, with larger plates, you get a bigger charge into your capacitor with the same voltage.