Old English oþer "the second" (adj.), also as a pronoun, "one of the two, other," from Proto-Germanic *anthera- (source also of Old Saxon athar, Old Frisian other, Old Norse annarr, Middle Dutch and Dutch ander, Old High German andar, German ander, Gothic anþar "second, other").
These are from PIE *an-tero-(source of Lithuanian antras, Old Prussian anters "other, second), which is perhaps a variant of *al-tero- "the other of two" (source of Latin alter), from root *al- "beyond" + adjectival comparative suffix *-tero-. Or the first element might be the pronoun *eno-, *ono- [Boutkan]. The Old English, Old Saxon, and Old Frisian forms show "a normal loss of n before fricatives" [Barnhart].
Meaning "different" is mid-13c. Sense of "second" was detached from this word in English (which uses second, from Latin) and German (zweiter, from zwei "two") to avoid ambiguity. In Scandinavian, however, the second floor is still the "other" floor (Swedish andra, Danish anden). Also compare Old English oþergeara "next year."
The other woman "a woman with whom a man begins a love affair while he is already committed" is from 1855. The other day originally (mid-12c.) was "the next day;" later (c. 1300) "yesterday;" and now, loosely, "a day or two ago" (early 15c.). Phrase other half in reference to either the poor or the rich, is recorded from c. 1600.
La moitié du monde ne sçayt comment l'aultre vit. [Rabelais, "Pantagruel," 1532]