Sheridan/Delenn (human/Minbari-Human Hybrid). Also subverted with Valen, and his wife, since even though Valen was actually Commander Sinclair turned to a Human-Minbari Hybrid. according to Word of God his wife was Catherine Sakai, who presumably went through the same process.
G'Kar is demonstrably fond of women of other species. At the end of the series it seems likely that Lyta Alexander is aiming to hook up with him long-term.
The Immortal and Darla and Drusilla: immortal "human"?/vampire/vampire.
Jasmine in Cordelia's body and The Beast: higher power/demon.
Angel and Nina: vampire/werewolf.
Marcus Hamilton/Harmony: human-like creature/vampire.
Willow/Saga Vasuki: human/demon.
Dawn and Kenny: human (technically)/demon. Yeah, check out the Jo Chen cover for issue 25 of season 8 to meet all your daily Squick requirements. There are tentacles.
Whistler's parents: pure-blood demon/higher being. They were killed for this.
Stefan/Elena from The Vampire Diaries. Stefan is a century old immortal (vampire) and Elena is an eighteen year old mortal human. This changed when Elena was turned into a vampire as well.
Matt/Caroline (human/vampire) in season 2. In fact, pretty much every relationship with Caroline falls into this: Tyler/Caroline (werewolf/vampire), Klaus/Caroline (vampire-werewolf hybrid/vampire), Jesse/Caroline (human/vampire). Although the latter turns into a vampire eventually.
There's also Damon/Katherine and Stefan/Katherine, back when the Salvatores were human. And Jeremy/Anna (human/vampire) falled into this, as it was before he became a supernatural hunter).
Moving to The Originals, we have Marcel/Rebekah; while both of them are vampire, flashbacks revealed that they started their romance when Marcel was a human a hundred years ago, and he was later turned by Klaus. Also, there's Marcel/Sophie (vampire/witch) and Elijah/Celeste (original vampire/witch).
John Crichton's brief pairing with Zhaan, and his encounter with Chiana in the past. His relationships with Aeryn Sun and Gilina Renaez too, considering the Bizarre Alien Biology of Sebaceans.
Scorpius (Sebacean/Scarran hybrd) had relationships with Natira, an alien of unknown origin, seemed to flirt with random aliens of the week (M'Lee, Ro'Na), had a relationshop with Sikozu, a Kalish and a bioloid, and all that Ho Yay with Crichton and Braca...
Moya's offspring (Living Ship/regular spaceship), though that was less "romance" and more "mad science experiment".
In Requiem for Methusaleh, Kirk falls in love with a woman who turns out to be an android, but it does not change his feelings.
Spock himself and Leila Kalomi (This Side of Paradise). He is forced by the spores into confronting his human feelings and tells her "I do love you".
Spock also fell in love and had a sexual relationship with another non-Vulcan woman, in All Our Yesterdays while under the influence of time displacement. In addition, a number of human or at least non-Vulcan women showed an interest in Spock at some point, including Nurse Chapel (desperately in love with him), Lt. Uhura (flirted with him in a couple of episodes) and Droxine, a human-looking princess (whose interest was reciprocated) from an alien planet in the episode Cloud Minders. His relationship with the Romulan Commander The Enterprise Incident) may or may not count; Vulcans and Romulans are an offshoot of the same species (and a fairly recent offshoot at that, especially given how long both species live).
Mr. Spock's parents, Sarek (Vulcan) and Amanda (human), are never depicted as anything but Happily Married.
Sarek's second wife, Perin, was also human, and they were also Happily Married. This led to fandom speculation that Sarek had a human fetish.
Tasha Yar had a one-night stand with a "fully-functional" android, Data.
The Tasha Yar look alike Romulan, who was actually the daughter she had in an alternate timeline with a Romulan General.
Riker never seems to be interested in any female unless she is extraterrestrial, and apparently is irresistible to all of them. Good thing the show ended before he got around to the Horta; that acid's a bitch to clean off.
In the 2009 film, young Spock has a romantic relationship with Uhura in the alternate timeline while Kirk, unsurprisingly, has a fling with Gaila, a green-skinned cadet from Orion.
In the Star Trek: Deep Space Nine episode "You are Cordially Invited,", Martok's wife has some serious reservations about Worf marrying a non-Klingon.
In another episode Quark (Ferengi) and Grilka (Klingon) get married for political reasons. There is some mild attraction between them, but they get a divorce, then later have one last fling. Grilka's loyal family servant is at first disapproving, then later resigned to their attraction. Her bodyguard, on the other hand, is quite violent in expressing his disapproval.
Quark and a Cardassian woman.
Odo and Arissa in "A Simple Investigation," and later Odo and Kira. The relationship between Kira and Odo has the extra twist of Odo not even being actually humanoid. Most of the day he spends in the shape of a play dough man, but the natural form of his race is a viscous liquid into which he turns back at night. And yes, we have given the Power Perversion Potential due consideration.
Several interspecies romances and even marriages between the main and recurring characters happen: Jadzia Dax and Worf (Joined Trill/Klingon), Kira Nerys and Odo (Bajoran/Changeling), Rom and Leeta (Ferengi and Bajoran), Ezri Dax and Bashir (Joined Trill/Human) and a recurring mixed species character Ziyal, the daughter of the Cardassian baddie Dukat and one of his Bajoran mistresses.
In fact, even setting aside Ezri, Bashir seems to prefer non-humans— he had a long-standing crush on Jadzia Dax (joined Trill), a short-term fling with Melora Pazlar (Elaysian), and a moderately-long relationship with Leeta (Bajoran). And Elim Garak (Cardassian) fell in love with him, but has yet to tell him as of the Star Trek: Deep Space Nine Relaunch.
And perhaps the most extreme example, Ben Sisko was half human, half god.
In the episode "Melora", Dax recounts an anecdote of two people who didn't even breath the same type of air getting together and staying together for 57 years. Even better, she's telling the story to try to convince Melora not to let inter-species differences get in the way of true love.
B'Elanna Torres on Star Trek: Voyager often comments that her childhood was not a happy one, because her father "Couldn't handle living with one Klingon, let alone two".
The perils of this are explored in "The Disease" when Harry Kim has a passionate affair with an alien woman without checking with his doctor first. No, he doesn't get an alien STD - the disease is love. Unfortunately the attraction is not only emotional but biological as well. Plus Harry's skin tends to glow, which must make sex in the dark easier but seriously squicks his friends. Harry should have known better though; in "Favorite Son" a race of sexy space vampires try to suck out all his DNA - as they have few males it's the only way they get enough genetic material to continue their species.
Kes (Ocampa) and Neelix (Talaxian) had a relationship for a while. (Neelix had rescued Kes from a life of slavery on Kazon.) They later broke up because Neelix was being too overprotective, and Kes' last contribution to the crew (where she uses her Psychic Powers to hurl Voyager and its crew safely beyond Borg space, 9,500 light-years closer to Earth) pretty much ruins any chance of them getting back together. (Of course, given that Ocampa typically only live about nine years, it likely would have been a Mayfly-December Romance if it had worked out.)
Q is constantly pursuing Janeway, but while he promises that foreplay with a Q can last for decades it appears the actual act only lasts a second to the outside observer ("The Q and the Grey").
Star Trek: Enterprise, where humans had only been in contact with extraterrestrials for less than a century and sometimes still get squicked over the idea of romancing them. But this didn't stop Reed and Trip from being distracted in the first episode by a pair of alien dancing girls, and no less than three human crewmembers (Reed, Archer, and finally Trip for the win) from drooling over T'Pol at some point or another.
It is hinted that even farther in the future, the 30th century, interspecies relations probably became very commonplace. The time traveler Daniels mentions that he is "human, more or less" implying that he may have some alien genetics. The body of another time traveler whose trip didn't go so well was also examined and found to be a hybrid of numerous species, including human, Vulcan, Rigellian and Terrelian.
The episode "Dear Doctor" had a female human (Crewman Cutler) getting interested in Denobulan doctor Phlox. Whether his sixteen-inch tongue is part of the appeal was not mentioned, but the good doctor did caution her on the cultural differences of his species (Denobulan males are somewhat inhibited, but on the other hand have polyamorous marriages - Phlox has three wives who each have two other husbands). Likewise Trip is squicked out when one of Phlox's wives puts the moves on him and Phlox is excited rather than annoyed.
Star Trek New Frontier manages to include several Human/Xenexian relationships, plus Human/Thallonian and Xenexian/Thallonian.
Tokusou Sentai Dekaranger has Doggie Cruger, an anthropomorphic dog, who has feelings for his subordinate, the half-human half-swan person Swan Shiratori (whose own parents must have fit this trope). This plot element wasn't retained when Dekaranger was adapted into Power Rangers S.P.D. and Cruger's counterpart was married to a new character of his own species (though there are a few hints that Swan's counterpart Kat does have feelings for Kruger).
The next series, Magiranger, has the Rangers as Half Human Hybrids, part human and part Sky Saint/Heavenly Saint. This is underplayed, though. Also, Urara winds up paired with another Saint, Hikaru.
Magiranger's Power Rangers counterpart, Power Rangers Mystic Force, has several interspecies Last Minute Hookups, such as Leelee and Phineas (Vampire (or at least born from a vampire if not one herself) and troll/goblin hybrid), Toby and Necrolai (human and (ex-?)vampire), Madison and Nick (human and Human Alien from mystic dimension), with a little subtext between Daggeron and Itassis (mystic Human Alien and the highest-ranking demon now that the Big Bad is gone) for flavor.
It was present as early as Power Rangers Zeo, when Billy chose to stay on Aquitar because he had fallen in love with a colleague who'd helped him find a cure for his aging disease. Notable in that she was amphibious, and he was actively chosing to live long-term on a planet where most all life goes on underwater. Billy, despite being a blue ranger, does not breathe water. Hey, Love Makes You Crazy.
Kermit: Me? In love with a pig? Wait 'til I tell the guys in marketing! Ha ha! Maybe you expected me to go HOG-wild? Perhaps you could bring home the BACON! Ahhh... the sounds of love, SU-EEEEE! Oink, oink.
Also, Gonzo, whose species was unknown at the time but is now said to be some kind of alien has an attraction to birds, especially chickens, and in one case, a cow.
Brooke Shields: Is something wrong? Masterson Rat: Do you believe in interspecies dating? Brooke Shields: Well, I've dated some rats before, if that's what you mean.
It got weirder in Muppet Treasure Island. Benjamina Gunn (Miss Piggy) apparently had relationships with the humans Captain Flint and Long John Silver, the former of whom abandoned her on the island after their relationship ended. Her former fiance Captain Smollett (Kermit) seemed disturbed by this revelation, but it may have been more because of her promiscuity than the interspecies aspect.
Piggy's been known to throw herself at hunky male humans on The Muppet Show before. Christopher Reeve comes to mind. Also Patrick Wilson, drummer for Weezer, in the "Keep Fishing" video. Neither one reciprocated.
Wizardsvs Aliens: Human Wizard Tom Clark and Lexi of The Nekross. After several close moments across series one and two, the two become trapped in the mystical Neverside realm where magic reins surpreme and where time passes differently for any who serve there (i.e, years pass in this realm while hours pass in our own). In between searching for Lexi's brother, the two reveal the true extent of their feelings and consumate their relationship, producing a child they name after Tom's friend Benny. Ultimately Benny arrives and the family attempt to leave the Neverside with Lexi's brother, but upon leaving, all they had accomplished in the Neverside, including their son, vanishes from existence. Tom and Lexi mourn the loss of the child, and go back to their seperate lives amongst their own people, with the memory of their days together gradually fading until it feels more like a dream.
Out of This World: Donna (Human) and Troy (Antarian), Troy is apparently a Human Alien, though the only time he actually appears "in person", he's a somewhat abstract ghostly form. For the rest of the series, he only "appears" by way of a communication cube, which the other characters often treat as though it actually physically is Troy.
Space Cases does this with the hinted feelings between Harlan and Catalina, Harlan and Suzee, Radu and Elmira, and Radu and Suzee. Granted as a kids show none of these went anywhere, but its still worth note. However excluding Elmira (who is a proper Green Skinned Space Teen) every alien in this series is a Human Alien. Also, aside from Radu, Suzee & Elmira, the other "aliens" are actually descended from genetically altered humans created to live on other planets in the solar system.
Tragically played with in the CSI: Crime Scene Investigation episode "Fur and Loathing"; while all the characters involved are physically human, the victim was accidentally killed as an indirect result of his new flame's former boyfriend poisoning him with castor oil for stealing his girl... all on the basis of fursona species segregation (the victim was a raccoon, the girl a lamb, the boyfriend a wolf).
Hyperdrive. Hilariously spoofed in the compulsory sex education video watched before a First Contact mission. We don't see it (fortunately) but the crews' reactions to what they are watching show it would make even Kirk think twice.
"Let's learn about another Alien Sex Disease. This crewmember had intercourse with a Glygonthian octopoid. Let's take a close look at his genitals. Pustules have developed, and on the pustules: warts. Soon, his entire groin explodes, leaving five baby octopoids, each with his face. Remember, Alien Sex is Danger Sex."
In V, Willy the kind alien and the human Harmony Moore had a genuine romance, unfortunately cut short by her death in the second TV movie.
The Daily Show did a short piece on a biologist claiming that humans are more closely related to orangutans or something. At the end, we see John Oliver and an orangutan doing all the romantic stuff, terminating with Oliver hanging a "Do Not Disturb" sign on his hotel room door.
Averted in The X-Files. Though various monster/human relationships are seen, when one character thinks that the reason an alien took human form was because he fell in love with an Earth woman, the alien just laughs (it turns out he fell in love with baseball. And laughter).
In Roswell, of course, Max, Michael and Isabel, who are bio-engineered human/alien hybrids have their human significant others. It was never explained if they would eventually be able to have children though it was implied in the tie-in books that Max and Liz would have two children in the future. Zan, Max and Tess' offspring shouldn't count since both Max and Tess are hybrids of the same kind.
In Alien Nation, an on-again-off-again romance develops between human cop Matthew Sykes and Newcomer Cathy Frankel.