Hola,
yo creo redordar que cuando arranca el AVR, las entradas están en HI-Z (PORTxn a 0 y DDRxn a 0, que es lo lógico, por otro lado, tras un reset).
Lo suyo es que, como comenta @fm, las entradas que no estén conectadas a ninguna lados las pongas en pullup o como salidas, principalmente para reducir consumo y ruido electrico (no es bueno dejar entradas flotantes en tecnología CMOS).
El ruido, además de por la alimentación (que personalmente lo veo menos probable en tu caso, al estar alimentándolo a 9V, con marjen suficiente como para que el rectificador del arduino filtre algo - a no ser que el transformador sea lo que técnicamente se donomina como "una caca"), te puede venir por los cables que corren paralelos a los de 220V (la normativa de baja tensión exigen que cada circuito de la casa vaya por tubos separados, pero claro, eso se lo explicas tu a tu mujer 
).
Los cat5 no tienen malla. Puedes probar un cat6 conectando la malla sólo al lado del arduino. Además, estás usando los cables ethernet como simples conductores. Los cables ethernet son precisamente tranzados (twisted) para usar transmision diferencial de manera que cuando hay ruido EMI impulsivo (como cuando enciendes un fluorescente, por ejemplo), la diferencia de tensión entre los hilos se mantiene constante porque afecta de igual manera a ambos hilos. Puedes usar un diseño de ese tipo, aunque son más complejos, pero mucho más inmunes a interferencias EMI.
Si no, como mínimo, pon un filtro RC a la entrada del arduino, delante del pulldown. Por ejemplo, el pulldown entre gnd y y el pìn. un condensador entre gnd y el pin (cerámico, de algunos nanos) y una resistencia en serie con la linea de unos 100ohm. Aunque no sé si será suficiente, por los pedazos de picos que dices que tienes.
Si el ruido te viniese por la alimentación (por una bajada brutal de tensión 220V durante unos milisegundos), podrías mejorar el filtrado aumentando la componente C del filtro de salida del transformador. Es decir, poniendole un condensador gordote (>1000uF) a la salida del transformador.
Los transformadores caca, caca, caca sólo tienen un transformador y un rectificador de diodos de onda completa (4 diodos, vamos). Evitalos ... si eso es lo que tienes, ni idea de como te ha estado funcionando bien la cosa hasta ahora.