If this is really what you want:
Think "every thing was going well until the <big evil race> came"
If I understand you correctly, it would work if these guys were pretty - through - extremely evil. So campaign plotlines like:
- Humans nearby are attacking us (they were leaving us alone until the <big evil race> came)
- My favorite villagers have been dragged away by something horrible (they were doing well until the <big evil race> came)
- Aah! <big evil race>! Evacuate the town!
- We need heroes to track the <big evil race> down! Where are they coming from?
- The <big evil race> is implacably evil. We need to destroy them for good!
- Why on earth are our political leaders so evil? / Dismissive of the <big evil race>? Oh, no! They're working for the <big evil race>!
I'd definitely go with a hierarchy of related aberrations.
For that, I'd suggest aboleths at the top, taking the place of elder brains in illithid brine pools. This gets the "villagers kidnapped for horrible ritual" plot line right away. Of course, the aboleth have some skum slaves. But the lieutenants of the aboleths would be mind flayers (think of them as tadpole illithid, and it works great). Just below them, mix in some half-doppleganger mind flayers for infiltration politics (why are the Humans attacking? Why are our political leaders so evil?). Finally, under the mind flayers, put Umber Hulks (or throw the half-illithid template on an umber hulk - "Evacuate the town!"). So now you've got an incredibly evil hierarchy:
Skum at the bottom (direct servants of the aboleths, and help for individual mind flayers, also a great low-level encounter).
Umber-hulks in the middle
Half-mind flayer Dopplegangers
Mind Flayers
Aboleths
Basically, you still get your good race vs. evil race war, but you never have to cope with "what about the baby orcs?" Having run a humans vs. aberrations campaign, I can tell you players get MOTIVATED to kill off those suckers.