Why is voltage inversely related to capacitance? $C=\frac{Q}{\Delta V}$ More like charge on each capacitor plate increases $Q$, which increases $C$. However, more like charge on each plate also increases $\Delta V$ right? Because compared to before the capacitor was charged, there was an equal amount of each type of charge and everything cancelled to $0$. But now when $C$ is charged, not only do lots of like charges exist in the same place, but right over on the other plate is a bunch of the other type of charge. Doesn't this create a potential difference between two points in space between which a strong electric field is generated? So as a capacitor accumulates charge, it increases in capacitance; yet simultaneously it gains voltage, and still manages to increase in capacitance despite the inverse relationship. 
What's wrong with this logic?
I've just read a thread about how even though $\Delta V=IR$, voltage can actually exist without current. So even though the capacitor may be disconnected, it still has a voltage. My question applies to all possible states of a capacitor; including charging, discharging or charged capacitors.
 A: What you have written about more charge means a larger capacitance is not true.
The capacitance of a conductor depends on its dimensions and its composition.
For an ideal parallel plate capacitor the capacitance is $\dfrac{\epsilon A}{d}$ where $A$ is the area of the plates, $d$ the separation of the plates and $\epsilon$ the permittivity of dielectric between the plates.
For such a capacitor it is found that the charge stored (on one of the plates) $Q$ is proportional the potential difference between the plates $\Delta V$, so $Q\propto \Delta V \rightarrow Q = C\; \Delta V$ where the constant of proportionality $C$ is called the capacitance.
A: Here are some things that may help:

Doesn't this create a potential difference between two points in space between which a strong electric field is generated?

Yes it does, and it is the Dielectric that exists between these two plates that prevents the like and unlike charges combining (or better to say it prevents the electrons stored on one side of the plate moving over to the other plate that has an absence of electrons. Strictly speaking there are still some electrons there). 
Now although there is an electric field between the plates due to the separation of charges the net charge on the whole capacitor is zero. There is hence a potential difference across the capacitor.
If you look at some capacitors you will see that they are marked with the value of their capacitance. The greater the capacitance, the greater the potential difference across it. The capacitance of $C$ of a capacitor is defined by $$\text{capacitance}=\frac{\text{charge}}{\text{potential difference}}$$ or $$C=\frac{Q}{V}$$ So the capacitance is the charge stored per unit potential difference across it.

So as a capacitor accumulates charge, it increases in capacitance; yet simultaneously it gains voltage, and still manages to increase in capacitance despite the inverse relationship. What's wrong with this logic?

Nothing, you are correct. Those that make capacitors desire a capacitor that can store (separate) as much charge as possible without much of an increment in $V$, the voltage across the capacitor.

Consider the case where the voltage is a fixed constant:
For a uniform charge distribution over each of two parallel plates (basically a capacitor) the electric field strength is inversely proportional to the plate separation. So at constant voltage halving the plate separation doubles the field strength.
An increased field strength leads to an increased capacitance in accordance with Coulombs' law for electrostatic repulsion.  
