Что делать уклонисту, чтобы леголизоваться? И что его ждёт?

Если не повезёт-поимка, суд.
Статья 328. Уклонение от прохождения военной и альтернативной гражданской службы

1. Уклонение от призыва на военную службу при отсутствии законных оснований для освобождения от этой службы -
наказывается штрафом в размере до двухсот тысяч рублей или в размере заработной платы или иного дохода осужденного за период до восемнадцати месяцев, либо арестом на срок от трех до шести месяцев, либо лишением свободы на срок до двух лет.
2. Уклонение от прохождения альтернативной гражданской службы лиц, освобожденных от военной службы, -
наказывается штрафом в размере до восьмидесяти тысяч рублей или в размере заработной платы или иного дохода осужденного за период до шести месяцев, либо обязательными работами на срок до четырехсот восьмидесяти часов, либо арестом на срок до шести месяцев.

Статья 328. Уклонение от прохождения военной и альтернативной гражданской службы

1. Уклонение от призыва на военную службу при отсутствии законных оснований для освобождения от этой службы -
наказывается штрафом в размере до двухсот тысяч рублей или в размере заработной платы или иного дохода осужденного за период до восемнадцати месяцев, либо принудительными работами на срок до двух лет, либо арестом на срок до шести месяцев, либо лишением свободы на срок до двух лет.

2. Уклонение от прохождения альтернативной гражданской службы лиц, освобожденных от военной службы, -
наказывается штрафом в размере до восьмидесяти тысяч рублей или в размере заработной платы или иного дохода осужденного за период до шести месяцев, либо обязательными работами на срок до четырехсот восьмидесяти часов, либо арестом на срок до шести месяцев.

Ждёт до 2 лет тюрьмы, а потом всё равно служить.
Легализоваться легко - если сам придёт в военкомат, то ничего ему не будет (если никаких других криминализованных деяний в его действиях не было) .

Ждать до 27 лет, после этого придти в свой военкомат, получить там военный билет и жить дальше. Ну, кроме военного билета ещё получить сильную нервотрепку.

Начать с изучения русского языка...

Оформить официальные отношения с военкоматом, т. е в подавать на военкомат в суд постоянно.

А он чо, в розыске? Военкомат принимает призывников по месту прописки, если сменить место проживания, то, можно жить без проблем, и никто не будет парить моск с военкоматом. Будут определенные трудности с работой, но это смотря на что претендовать. Можно ведь по разному работать, и весьма успешно.

Что значит, чтобы легализоваться? Если вы лично подписывали повестку и не являлись по ней, то ждать 27 лет и 2 года с того момента, как объявили в розыск (срок давности по данной статье).