Hola Federico,
Como ya te sugirieron, tenes que hacer PWM sobre los motores para tener un arranque más suave. Hacer un lazo cerrado con encoders adicionales me parece que le quita la gracia al seguidor de líneas, que es justamente su simplicidad, lo que no impide lograr grandes resultados.
Una cosa que te ayudaría mucho creo, es acercar los sensores a la línea. En el video no se ve, pero me da la impresión de que están muy separados y por eso el móvil dobla demasiado cada vez, hasta que el sensor del lado contrario detecta nuevamente la línea. Si los ponés bien cercanos a la ésta, en cambio, la trayectoria sería mucho menos zigzagueante.
Adicionalmente podrías hacer una lectura analógica y no digital de los sensores de línea (creo que la EDU-CIAA no tiene entradas analógicas, en cuyo caso deberías usar un conversor AD externo) de modo de tener niveles en la detección de la línea y hacer que el duty del PWM de reacción de los motores sea proporcional a la lectura, es decir:
sensor "ve" poco negro-> corrección pequeña.
sensor "ve" mucho negro (el móvil llegó a la curva de 90º, por ejemplo), corrección grande.
Eso sería la parte proporcional (la P) del PID que sugiere Hugo. Si pudieras implementar el lazo PID completo, o agregar la corrección Integral (la "i" del PID), al menos, mejoraría mucho más aún, ya que la integral corrige muy bien pequeñas desviaciones constantes (diferencias constructivas entre los motores de uno y otro lado, por ejemplo).
A partir de ahí, el secreto -y la diversión- pasa siempre por optimizar la programación. Podés hacer análisis predictivo, adaptación del comportamiento a la traza de cada circuito, programar rampas de aceleración... Hasta sistemas de aprendizaje (una forma básica de AI) que vayan optimizando el comportamiento vuelta a vuelta, etc. Todo con dos simples sensores y mucha programación. Claro que sin lectura analógicas ni salidas con PWM las posibilidades se reducen mucho.
Saludos,
Miguel