Here, by android, I mean "an AI robot which looks and acts like a human." It shouldn't just be "Sex Robot". Emotions between both parties need to be involved.
At this time, there are two examples in my mind:
Relationship between Vision and Wanda in Avengers: Infinity War (2018).
Relationship between Data and Tasha in Star Trek: The Next Generation (1987). Once a Starfleet officer was acting against Data's rights saying "it" was a property of Starfleet, but Riker successfully countered this in court by showing Tasha's photo in Data's belongings and thus proving that there were some unknown variables in Data's positronic brain.
Which Sci-Fi work first showed a romantic relationship between a human and an android?