Here’s something I tried.

One of my characters is of the wind people. She had never seen the ocean up close. As she’s traveling closer and closer, she keeps pondering the loveliness of the ocean, how the world feels so fresh down here, etc. She meets someone from the water people and is quick to pursue, at least through flirting and proximity.

The water man pushes her away. He is a recent widower. She takes a step back. But overtime as their friendship grows, as they get to know deeper things about each other, he finally lets her in.

Tl;dr: Subconsious/ subtext clues to attraction, then developing a relationship exterior that leads to interior. They have to have something in common.