The Red Ajah may have been the only place Elaida could get what she wants. Lets consider the options.
Brown - Elaida and a lot of non scholars look down on them so no sell there.
Grey - Elaida sucks as a negotiator
White- The smallest Ajah with a completly alien mindset to Eliada's shoot from the hip/be guided by instinct approach.
Yellow- I can't see Elaida wanting to spend the rest of her life trying to make people better. For all the arrogance of the yellows at least at the start they want to heal people.
Greens/Blue/Red - A possibility

Elaida is very much, even in New Spring, a ruthless person. Her creed is do what needs to be done and damn the rules. The Greens are run like an army and love men. I don't think Elaida hates men but she is not comfortable around them either. I don't think Elaida would like having to be a good soldier (at least in the begining) and follow orders.

The Blues are more independant but Elaida is not a very good manipulater and for all the independance the Blues always struck me as having a code of conduct that they expect their members to follow. In the early books there were hints that Moiraine was getting in trouble with her own Ajah for her actions.

Lastly there is the Reds. Elaida want's power to save the world. Helping save the world with direct simple action like shielding and severing male channelers probably appealed to her simple black and white mindset who seems to have little in the way of patience. While the Reds are controled by their Head the attitude at the time was pretty hard core as evidenced by the Vileness.

I think that Elaida would have have picked up on that as an Accepted and figured that as the largest Ajah joining would give her political clout. She knew she would be one of the strongest sisters so she would eventually rise to the top. If you are upper management you have a lot more power as upper managment of a massive company that a smaller operation. Likewise their approach of doing what needed doing no matter what others though would appeal to Elaida.