I think an air-launched rocket would only be an incremental help. Chemical rockets on Earth are barely at 1/8th of orbital speed before they're out of most of the atmosphere (~60km altitude). You can't accelerate more without ascending because drag increases exponentially with velocity at a given air density.
Another way of looking at it—on a body with no atmosphere, the most efficient way to attain orbit is to be on the equator, point your spacecraft "east" (prograde to rotation), and elevate the nose just enough to avoid lithobraking on that mountain in the distance. If Earth were such a beast it would take roughly 7000 m/s delta-V to do this. IRL, because you need to get over the atmosphere first, it takes about 9000; the "gravity turn" is a compromise between losing energy to gravity/steering versus losing it to drag. So any exotic system—air launching a Saturn V is definitely exotic!—would help with efficiency, but I don't see that it would radically alter the situation.
In summary, as you said, the altitude is less important than the base velocity increase and atmospheric density reduction.
The former, because you're pushing maximum mass at t=0 (i.e. all the future fuel you need to burn), so any added velocity at rocket ignition time would compound throughout the rest of the burn cycle (or, to think of it another way, you've already overcome fully-fueled vehicle inertia with the benefit of atmospheric oxygen combustion).
Similar to how a multistage vehicle operates more efficiently, albeit without the benefit of atmospheric oxygen.
The latter, because you're essentially getting atmospheric density reduction for "free" (in terms of saving your on-vehicle propellant), and your propellant efficiency (in terms of propellant:velocity increase) scales better.
I.e. air-breathing aircraft + chemical rockets would work, as would other exotic solutions