Предложение, конечно же, сложноподчиненное (обратите внимание автора на наличие союзного слова когда). Но тире здесь возможно, и если автор настаивает на тире, то можно пойти автору навстречу: постановка тире не нарушит правил правописания. Правила оговаривают несколько случаев, когда в сложноподчиненном предложении вместо запятой может ставиться тире, один из таких случаев – расположение придаточной части перед главной.

Строго говоря, во второй части, которая представляет собой инфинитивное предложение, никакого типа сказуемого нет. Есть главный член односоставного предложения, выраженный — в данном случае — инфинитивом в сочетании со связкой (в настоящем времени она нулевая, а, скажем, в прошедшем времени обязательно обнаружится: ...а вот кошке к ее гнезду было не подобраться). Сказуемого, которое строилось бы по модели «формальная связка + инфинитив», в двусоставном предложении не бывает. Главный член односоставного предложения может описываться по формуле «главный член в форме такого-то сказуемого», если он действительно отвечает одной из существующих моделей сказуемого (Больного знобит). Здесь же и такого сказать нельзя.

Рекомендуется: со всесезонным покрытием.

Нормативными словарями такое прилагательное не зафиксировано, однако в практике письма встречается только дефисный вариант нижне-левый, что не противоречит действующим правилам. 

Вы совершенно правы в том, что названные термины должны писаться одинаково, поскольку они семантически и структурно однотипны. Непонятно, на основании каких статистических данных сделан вывод о том, что второй термин чаще пишется через дефис. К сожалению, в Национальном корпусе русского языка они не встречаются, а Яндекс в подборке регулярно (хотя и не без исключений) выдает слитное написание для обоих. Такое написание и следует для них порекомендовать.

В доступных нам источниках это выражение не зафиксировано. Вы уверены, что это именно поговорка (т. е. устойчивое выражение, воспроизводимое в речи), а не индивидуально-авторская метафора?

Это слова Александра Галича из стихотворения "Вальс, посвященный уставу караульной службы" ("Поколение обреченных"). Слова понятны в контексте стихотворения:

О, суконная прелесть устава -
И во сне позабыть не моги,
Что любое движенье направо
Начинается с левой ноги.

А потом в разноцветных нашивках
Принесли мы гвардейскую стать,
И женились на разных паршивках,
Чтобы все поскорей наверстать.

И по площади Красной, шалея,
Мы шагали - со славой на "ты", -
Улыбался нам Он с мавзолея,
И охрана бросала цветы.

Ах, как шаг мы печатали браво,
Как легко мы прощали долги!..
Позабыв, что движенье направо
Начинается с левой ноги.

И цитаты из устава:

Движение строевым шагом начинается по команде "Строевым шагом ─ МАРШ" (в движении "Строевым ─ МАРШ"), а движение походным шагом ─ по команде "Шагом ─ МАРШ". По предварительной команде подать корпус несколько вперед, перенести тяжесть его больше на правую ногу, сохраняя устойчивость; по исполнительной команде начать движение с левой ноги полным шагом.

Повороты в движении выполняются по командам: "Напра-ВО", "Нале-ВО", "Кругом ─ МАРШ". Для поворота направо (налево) исполнительная команда подается одновременно с постановкой на землю правой (левой) ноги. По этой команде с левой (правой) ноги сделать шаг, повернуться на носке левой (правой) ноги, одновременно с поворотом вынести правую (левую) ногу вперед и продолжать движение в новом направлении.

Запятая не нужна.

По формальному принципу запятая требуется, потому что союз когда не имеет второй части (когда... то): Кошкам, пользующимся метро, трудно понять, где их следующая остановка и почему, когда две линии метро пересекаются, это пересечение не обозначено как остановка.