In 部, the right side radical is called the large village radical.
For 陪, the left side radical is called the small village radical.
Why are their names different on different sides even though both are 阝?
They're both written as 阝, but they're simplified representations of two different kanji:
As you say, 邑 always appears on the right, while 阜 always appears on the left. Often, 阜 as 阝 is referred to as 阜偏（こざとへん)--the へん at the end tells you it's in the left-side position. Likewise, 邑 as 阝 can be referred to as 邑旁（おおざとづくり), where つくり indicates the right-side position.
The customary names of 部首 are somewhat arbitrary, and they don't always communicate the meaning they lent to the kanji when they were formed, or if they do, the connection to the meaning can be quite tenuous. Still, in the case of 邑, it's called おおざと because it represents a (large) village. Let's look at a couple examples of 邑 and see for ourselves:
So 邑 appears to represent large village, at least historically. 阜 on the other hand has only a loose semantic connection to "small village". Etymologically and in most kanji, it instead represents a hill or mound. It's a little more apparent in the older form, which you can see on chineseetymology.org. It has three parts arranged vertically, representing a terraced hill. Why then is it called こざと? By analogy to おおざと--the opposite of an おおざと is a こざと, and from appearances it is a 阝 written on the opposite side.
Let's look at some examples for 阜:
So we can see the "large village" and "hill, mound" meanings clearly, even if they're sometimes obscured, and we've covered how "hill, mound" became "small village". I believe this answers your question!
One last note: in modern Japanese, you're unlikely to see the characters 邑 and 阜 in their full forms unless you're using a 漢和辞典 or talking about kanji. I developed a little mnemonic device to remember which one to turn to in my dictionary (which is 縦書き, so this won't make sense if yours is 横書き and printed left-to-right):
Note: in this entry I relied on Kenneth G. Henshall's A Guide to Remembering Japanese Characters as a primary source for character etymology.
Perhaps not an answer, but the question is based on a false presumption that "even though both are 阝". While the radicals may visibly look similar, the kanji that they represent are quite different. For "big village", the character is 邑, while for "small village", the character is 阜.
As radicals, "big village" is properly written as ⾢ (U+2FA2) or ⻏ (U+2ECF). For "small village", it is ⾩ (U+2FA9) or ⻖ (U+2ED6). Notice that ⻏ (U+2ECF) and ⻖ (U+2ED6) are two entirely different characters. In Unicode, the first is called city while the second is mound radicals.