Are these sentences all OK and natural?
The sooner we leave off, the sooner we get there.
The sooner we set off, the sooner we get there.
The sooner we take off, the sooner we get there.

Question

Answer

The first is never used in this context

The second is a bit old-fashioned.

The third is what you are most likely to hear.

Answer

The second and third sentences are fine but I have never heard anyone say "the sooner we leave off"
You would simply say "the sooner we leave, the sooner we get there. 
Set off and take off are both idioms which both just happen to have the same construction.

Hope this helped :)