Может ли новый хостинг отрицательно повлиять на посещаемость сайта?

Нет, если только перенос не будет затянут и сайт будет недоступен, или если у хостинга будут забанены боты ПС и т.п.

Спасибо за обнадеживающий ответ. А например укоз? Я просто начинающий.. И тема вроде уникальная и не настолько распространенная..

Ещё говорят/пишут, что некоторые хостинги ограничивают деятельность поисковых и прочих ботов, и из-за этого часть посещений может быть потеряна. Так ли это?

Если да, то применяется ли это только к шаред-хостингу или к VDS/VPS тоже?