Vale, os digo.
He encontrado cuál es el problema. Si usamos el movil a 2k no va bien, se tendría que bajar a FHD+ para que Android Auto se vea correctamente.
Es muy curioso porque SOLO se ve mal cuando abres el Maps o Waze. Todo lo demás va genial (spotify, el home de Android Auto... etc)
No nos queda otra que esperar a que Samsung o Google sale una actualización para esto.