For a DC arc what you are looking for is called Paschen's law. Wikipedia knows about as much as I do, but in brief Paschen's law is a phenomenological model which gives the breakdown voltage for an electrode of given gap size filled with a gas at a given pressure. The breakdown is thought to be an avalanche process in which free electrons are accelerated by field in the diode and then slammed into gas molecules to break free more electrons. This only works best if the electrons have lots of gas molecules to hit, but no so many that they collide before having gained enough kinetic energy to break apart the gas. The number of gas molecules in-between the electrodes is proportional to $p d$ where $p$ is the pressure (i.e. density) and $d$ is the distance. This paschen's law gives a formula for $V(pd)$ which is the voltage at which breakdown will occur. There is a particular $pd$ for which breakdown is most likely which is referred to as the Paschen minimum.
Importantly we can expect many properties of a discharge to scale (roughly) with $V/pd$.
Now the situation can be more complicated with AC current. But if the breakdown occurs fast enough then the AC current can be thought of as DC. The electron mobility (pdf link to a Computed electron drift velocity in moist air by Wyatt 1967) in air depends on the ratio $V/pd$, but assuming that you are at breakdown and that you have a large $pd$ (i.e. not near the Paschen minimum) then you have a $pd$ on the order of 40 V/cm/mm Hg and a velocity on the order of 50km/sec. Assuming you have AC at 60hz then you are near the top of the sin wave for at least 2 ms and so electrons can drift through 50 m. Now that doesn't mean that you will be able to arc of 50 m, you still need enough collisions to cause a breakdown, but I think 1m would be a good scale distance (and require 3.4 MV--more than you could reasonably achieve).
Of course there can be much more to the puzzle than that. For example, you observed that you could stretch your arc. This is likely because after first establishing breakdown you created a plasma which helps conduct the current. But for an extended arc there is also the trouble that every half cycle the applied field goes to zero and the gas starts to recombine. There is also a question of geometery since Paschen's law applies to parallel plates. Moreover at higher AC frequencies (like RF waves) then you get new phenomena. For example if you were at RF and added magnetic fields and build an inductively coupled plasma.
As I look over my post I will add another reference which seems quite useful for phenomenological describing arcs. And lastly be safe! As you must know by now, the voltage/currents you are using are no joke.
Edit
Since you describe you describe arcing between 'contacts' I might suppose that you are using some sort of 'tip' or pointy contact to arc.
If we use two spheres then we can calculate the voltage (i.e. image charge method). For two infinite planes we have $E=v/d$, but for two spheres (far apart from each other) then we have $E=V*a/d^2$ where $a$ is the radius of the spheres. If the spheres are put close--$d \approx a$--then there is significant field enhancement (in the form of extra image charges) which will help lead to arcing.
In practice the result will greatly depend on the geometry of your problem!
Some googling shows a result for cylindical diodes--"Minimum Breakdown Voltage in Cylindrical Diode"
Best Answer
Paschen already did. See Paschen's Law
The underlying physical intuition here has to do with the mean free path of electrons, electron-impact ionization and coulomb collisions.
Electric fields will separate electrons from atoms in a gas, for example, and cause them to accelerate. Those electrons will (1) lose energy (coulomb collisions) on other electrons as they accelerate and (2) may knock out other electrons (impact ionization) if they are sufficiently energetic. These are two competing terms.
If for example, the mean free path for electron-electron collisions is small compared to the gap size, and the electric fields are relatively low, then (1) will dominate and an arc is not sustainable.
On the other hand, if the mean free path is on the order or larger than the gap size, and or the electric fields are very large, then (2) will dominate and an arc is sustainable.
If you want a characteristic length, the mean free path is a good rule of thumb. It should be obvious based on the above discussion how the voltage of the source and the gap come into play (voltage / gap = electric field). The resistivity of the medium in the traditional sense (the cold matter resistivity) doesn't matter. Once you have the arc, what matters is the plasma resistivity which depends largely on the mean free path for coulomb collisions. The shape of the electrodes can affect the electric fields, especially near the electrodes.