But then you admit that an intelligence predisposed to evil is not necessarily incongruous
There are ways we could imagine having a type of creature who has free will, but is pretty universally evil.
Let us imagine, for example, that Freudian psychology had some validity - it is simplified model, with issues, but will work descriptively for our purposes. Very, very roughly, we have a model with an Id - the instincts, Ego - understanding of reality, and the Superego - the morality.
Now, imagine a creature who, in that framework, had a massively underdeveloped superego. They understand, for example a certain kind of morality with regards to rearing of young of their own species, but that's about it. Or, imagine a creature that is physically/neuro-biologically incapable of anything more than proximal empathy - if you are not one of its best buddies, it is fundamentally incapable of registering that you have emotions or feelings of your own.
This is the model of evil as something a human would call a psychological limitation or cognitive deficit. The thing has full ability to choose, but there are some ideas that simply don't occur to it - it never occurs to an orc that your pain is worth consideration. It can still plan and be intelligent and choose, based on its own needs and desires. But your needs and desires is it simply not capable of caring about.
The result, from a human point of view, might be a sort of violent sociopathy, which in game terms we might just call Evil.