Efectivamente los sprites solo pueden tener un máximo de 16x16 pixels de tamaño y un solo color (siempre hablando de MSX1). Por lo tanto, efectivamente, todos los personajes de los juegos MSXeros que ves que tienen varios colores es que, efectivamente, hay un montón de sprites solapados uno encima del otro, tantos como colores.
Claro, que hay que tener cuidado de no utilziar muchos sprites por cada personaje, ya que, como sabrás, el VDP solo nos premite tener 4 sprites por linea horizontal (si pones un 5º, éste desaparecerá). Aunque para evitar ésto hay varias rutinillas por ahí de rotación de sprites, donde se sustituye la desaparición del quinto sprite por un parpadeo de los sprites implicados (ver thread
"Evitando la regla del 5º sprite")
En cuanto a que si Popolon tiene un rollo sexual con Medusa, pues realmente no lo se... eso sí, que no te lea Afrodita, que fijo que se pone celosa