You know the difference between the and a(n).
The difference between the other and another in the singular is like that:
The other person - another person
In the plural you always use other.
So, applying that to your examples:
If I saw my boyfriend with another girl. - a different girl (not me)
If I saw my boyfriend with the other girl - that particular different girl (not me)
If I saw my boyfriend with other girls - this would probably mean a series of different individual other girls, on different occasions.
If I saw my boyfriend with the other girls - a different group of girls (not the girls we have already specified).