I've been thinking of a sort of sequel to the original Red and Blue Rescue teams. The protagonists of that game would become the antagonists, recruiting Shadow Lugia and casting the world of the Red and Blue games into shadow. Alakazam flees by teleporting to another region and warns the Pokemon there from an invasion from the "shadow" world. In that world, the game takes place, and you're a rescue team that saves the Pokemon in that region from Shadow attacks (caused by unstable energies from Alakazam teleporting, as Shadow Lugia tried to stop him), then team up with the protagonists of the second games (Time/Darkness) in that region to secure a portal to the "Shadow" world to stop Shadow Lugia.
The personality test would include all 24 possible natures for 30 starter characters:
the 18 gen 1-6 starters, available for both genders.
For each gender, six gender-exclusive starters, bringing the total to 30.