¿Con un relé? No puedes.
Los contactos del relé están abiertos (lámpara completamente apagada) o cerrados (lámpara completamente encendida) y no pueden cambiar un relé lo suficientemente rápido como para dar un efecto de atenuación.
simular este circuito : esquema creado usando CircuitLab
Lo que estás buscando es un atenuador controlado por triac.
simular este circuito
En este caso se utiliza un triac optoacoplado. Su micro encenderá el LED D1 en el punto apropiado en el semiciclo de la red al encender el triac. El triac permanece encendido hasta el próximo cruce por cero de la red y luego se apaga. A 100 (50 Hz) o 120 (60 Hz) medias ondas por segundo, el parpadeo no se nota.
Su código tendría que monitorear de alguna manera el cruce de la red principal, aumentar la demora en el disparo del triac y pulsar el optoaislador en el momento adecuado. Un montón de ejemplos en una búsqueda web.