Используйте не реле, а полевой транзистор и ШИМ. Это позволит плавно наращивать ток в двигателе, увеличивая коэф. заполнения ШИМ.
Если ардуина запитана от 12В, то можно немного смягчить
симптомы, подключив её
через диод, а за ним уже конденсатор по питанию ардуины, поближе к самой ардуине... (обведено красным)
Так же есть вариант, что у вас ардуина подключена напрямую к обмотке реле и это она уходит в кз при попытке открыть реле :)
Либо при пуске двигателя возникает мощная наводка, если он близко лежит.
Используйте ступенчатый запуск на двух реле! Сначала подключать реле с мощным токоограничительным резистором (от того же ВАЗа), потом включать второе реле, которое исключит этот резистор,
хотя это уже прошлый век это решение проверенное временем!