Bueno, pues sí. En fire red lo mejor sería poner ambos minisprites en el mapa que sea y hacer un script de nivel con un checkgender. Dependiendo del personaje que eligieras aparecerá como rival uno u otro. Luego sería un script normal en los encuentros con él, claro que con algunas diferencias como a la hora de luchar y cosas así.

Requiere un cierto nivel para eso, pero vamos, nada que no se pueda conseguir practicando. Aunque si no tienes mucha experiencia te recomiendo que empieces antes por lo más básico ;D