Kinetics of molecule reacting with another of itself
If you had double the amount of $\ce{O3}$, wouldn't the rate simply double (instead of increasing as the square)?


No. You seem to be really close to understanding why this would not be the case, though. To help bridge the gap, let's consider the kinetics of a general bimolecular reaction:

$$\ce{A + B -&gt; C}$$

We know that: $$\ce{\frac{d[\ce{P}]}{dt}} \propto \ce{[A][B]}$$ 

and that doubling $\ce{[A]}$ doubles $\ce{\frac{d[\ce{P}]}{dt}}$ because when we substitute $[2\ce{A}]$ for $\ce{[A]}$, we get: $$\ce{\frac{d[\ce{P}]}{dt}} \propto [2\ce{A][B]}=2\ce{[A][B]}$$ 

If $\ce{A}=\ce{B}$, however, then it follows that we must also substitute $[2\ce{A}]$ for $\ce{[B]}$, which then gives us: $$\ce{\frac{d[\ce{P}]}{dt}} \propto [2\ce{A}][2\ce{A}]=4\ce{[A][A]}=4\ce{[A][B]}$$