In Dragon Bones, the Hurog family is distantly descended from dragons. Who are sentient, no worries. There is also a more recent interspecies romance, Axiel is half-dwarf, and his parents seemed to be fond of each other.
In Shapeshifted by Cassie Alexander, the hero Edie has several love interests none of whom are human. There is the (sentient) zombie Ti, the shapeshifter Asher, and Hector, who actually is Asher in disguise. Other humans have romances with vampires.
In The Sorceress's Orc, human protagonist Vervain falls in love with her bodyguard Riyu, an orc.
In Dora Wilk Series Dora (a witch) and Miron (devil) are having a romance. In the background, czart (half-devil) Leon is romancing wiccan (in-story kind of a nature witch/fairy) and plans to marry her. More cases like this are implied in Winner Takes It All when main characters discover a "school" where Fantastic Racist Raphael is keeping half-angel-half-magical kids.
Sgt. Bill Booley and Windsweet from Legion of the Damned. Booley is a member of a futuristic Foreign Legion, while Windsweet is a Naa, a cat-like humanoid alien. Booley is taken prisoner by Windsweet’s tribe, romances her, kills her abusive suitor in an ‘honor duel’ and consummates the relationship before escaping the village with the help of the humiliated chieftain, Windsweet’s father. Before the end of the book the two will unite the humans and Naa against far less friendly reptilian aliens and conceive a son. Their hybrid son continues the family tradition by romancing human and Naa alike.
Wet Goddess: Recollections of a Dolphin Lover: nuff said
Piers Anthony seems rather fond of this trope.
Particularly Squick-inducing pairings are hinted at but not shown explicitly in Xanth, where any two creatures of opposite gender who drink at a "love spring" will fall in lust and (successfully) interbreed. This is the origin of most of the sentient species in the series including harpies (human/vulture), centaurs, etc. We also have a story where an ogre/human hybrid falls in love with a human/nymph crossbreed, the child of a centaur/hippogryph (eagle/horse hybrid) and all manner of others.
In Xanth, EVERYTHING is intelligent (at least to some degree), though not everything can communicate in the human tongue. And in all fairness, Biology is not at all involved. Babies literally arrive via the stork, so there's less squick than it seems.
However, there's the process of summoning the stork...
In his Apprentice Adept novels, we are "treated" to human/unicorn (the unicorns can shapeshift to human), human/robot, human/werewolf, human/vampire, and human/alien relationships, just to name a few.
Incarnations of Immortality series: human/ghost, human/demoness (three times, one rather Squicky), human/damned soul. Zane/Luna is an aversion, as they're both human (though he's the current Death).
Examples from The Mortal Instruments: Played straight with Magnus and Alec. No punintended. Every witch and warlock is the offspring of a human and a demon (though Word of says that most of these cases are rape, not romance), in City of Ashes Isabelle is dating a faerie knight. The fey themselves are the offspring of demons and angels. Jocelyn and Luke and Isabelle and Simon, as of City of Lost Souls, are in the same vein as Tonks and Lupin from Harry Potter, with their lycanthropy and vampirism respectively being more like diseases than a genetic trait, though there are born werewolves in-universe. Helen and Mark Blackthorn are half-fey as well.
Example from The Infernal Devices include: Will's parents, a Mundane and a Shadowhunter, Tessa with both Will and Jem, Sophie with Gideon, also a Mundane and a Shadowhunter, Benedict Lightwood and an unknown number of Demonesses, Magnus and Camille Belcourt, a Warlock and a Vampire respectively, Camille again, with her former lover, a Werewolf, and Magnus again, with Woolsey Scott, also a Werewolf. Jessamine also develops feelings for Tessa's brother, Nate, though this may just be out of her desire to be a Mundane.
Though Shadowhunters and Mundanes aren't exactly a different species, they are different enough to qualify. To make another Harry Potter comparison, it is the equivalent of a witch or wizard marrying a muggle.
Asimov had first explored this in one of his classic robot short stories, Satisfaction Guaranteed, where a frustrated housewife falls hopelessly in love with an early human-replicant robot. In the anthology notes Asimov expressed surprise that he received a lot of mail from women who shared the heroine's attraction to the robot. He shouldn't have: it is described as the classic romantic hero, attentive, supportive, insanely helpful and physically perfect, and (this being Asimov writing in the '50s) expressing its love only in the occasional passionate kiss.
Quozl is about cute rabbit-like aliens who eventually integrate into human society, and believe in frequent sex anytime, anywhere with any compatible intelligent species as a legitimate means of blowing off steam. The book establishes that once Humanity understood that social more, the Quozl quickly become very popular company. On the other hand, humankind was the only other intelligent species they'd run into.
Spellsinger is set in a world where humans and anthropomorphic animals live side by side including romantic and sexual encounters. Subverted in that, while the Earth-import protagonist feels attracted to an ermine stripper, he's dismayed by his own feelings and never actually goes native enough to join in this trope's fun.
The Humanx Commonwealth series features a wide variety of alien species. Most of the time the biological and social incompatibilities are treated seriously, although mental compatibility between some humans and the insectoid Thranx occasionally reaches Ho Yay proportions. There are some memorable scenes in Bloodhype, however, where a particularly flirty character discusses ways to erotically stimulate members of other species, intentionally and quite successfully Squicking out her companions.
In Sliding Scales a reptilian AA'nn falls in love with the protagonist Flinx. She doesn't confess her love until already mortally wounded and dies in his arms, prompting one of many incredible Unstoppable Rages and discovering a new Limit Break technique, more or less a literal application of the Death Glare.
Played in an unusual fashion in The Dark Tower, where Roland has sex with a succubus in order to get information from it. In a later novel, the same succubus, now in male form, rapes Susannah and impregnates her with Roland's sperm. When the resulting child is born, it's a cannibalistic human-spider hybrid. This is exactly how medieval folklore said succubi/incubi worked. That a demon could never create true sperm or truly mate with a human, so demon children were the result of a succubus stealing a man's seed, turning into an incubus and raping a woman. Succubi/incubi themselves have no "real" gender, being spirits. Also, Rhea and her snake...
The Wanderer included romance with an off-world female from a feline race. Think serious scratches down the back.
Fafhrd and the Gray Mouser have non-human girlfriends among their conquests, including a ghoulnote Ghouls of Nehwon seem to be just a race of humans with invisible soft tissues. They look like skeletons but feel like normal humans. Also they used to steal and eat bodies from cemeteries, but seem to have long stopped that. and a sapient rat-girl who is part human. In fact the rat city under Lankmar seems to be the result of many generations of a merchant family magically shrinking themselves and screwing rats.
Deconstructed in several H.P. Lovecraft stories that show how squicky such a thing would actually be - e.g. "Facts Concerning the Late Arthur Jermyn and His Family" (an ape) and "The Shadow Over Innsmouth" (a race of hideous fish-frogs known as the Deep Ones). On the other hand, considering Lovecraft's peculiar attitude towards intraspecies romance, they could also be seen as not so much a Deconstruction but just a different brand of Fantastic Racism allegory... Let's face it: the guy was squicked out when he discovered that his great-great-grandmother was Welsh. In a way, this could be seen as a Real LifeDeconstruction of Squick itself.
In Kraken, also by Mieville, a human man and a female djinni (treated in this universe as fire elementals) have a relationship and a daughter. The reveal comes with the protagonist realising that a photo which he thought showed father and daughter standing by a bonfire was actually a full family portrait.
Sometimes you get interspecies sex without the romance, e.g. Rishathra in Larry Niven's Ringworld series (it's a bonding/peace ritual between hominid species, plus an opportunity to get lots of action without the risk of unwanted pregnancies).
Averted with species that are too different, however. The marooned kzinti Chmeee eventually had to invade the Map of Kzin in order to score. "Too different" doesn't have to be that extreme; one humanoid species seldom has rishathra because few other species can function underwater.
Niven also discusses interspecies sex in the short story "Shall We Indulge in Rishathra?", found (along with the Superman essay, mentioned above) in the short story collection N-Space.
The Draco Tavern series contributes to the subject in the short story "Breeding Maze". Another story from that setting, "Smut Talk", also counts, as it explores the possibility of a sexually transmitted Alien Invasion.
Eragon falls madly in love with Arya, an elven ambassador. Lots of Love Hurts ensue.
First and foremost is Angua (werewolf) and Carrot (biologically human, raised and identifies as a dwarf). Their potential children are a plot point in Feet of Clay. In The Fifth Elephant it is hinted that Angua also used to have a relationship with an ordinary wolf, implied to be the descendant of a yennork (a werewolf stuck permanently in one form, in this case wolf).
Lupine and Ludmilla Cake: While they're more-or-less the same thing (werewolves), one's a wolf who turns into a wolf-man during the full moon, and the other is a human that turns into a wolf-woman (they more or less meet in the middle). Somehow, they make the relationship work, despite only having one week-in-four per month in which they are the same bodyshape. The secret and beloved dark heart of this meme is that that's very much their affair, and none of our business... or to put it another way, maybe they are happier than you think.
There's also the implied relationship between Lord Vetinari (human) and Lady Margolotta (vampire).
It's also been stated (or at least implied) that Nanny Ogg has some dwarfish ancestry, albeit several generations back.
Casanunda will romance (or at least boff) any female who'll hold still long enough, pretty much regardless of species.
In Snuff, there is a one-page mention that a dwarf and a troll have set up a house together in Ankh-Morpork. The same book also has Nobby Nobbs beginning a relationship with a female goblin. Of course, Nobby is also so odd-looking that there's a decent chance he has some goblin ancestry as well.
In Raising Steam a wedding between a human and a dwarf is crashed by dwarven extremists, though most of the integrated town thought they were a good match, and it only diminished popular support for the extremists further. They also show the beginning of a relationship between a dwarf and a troll at one of the new train stations.
In Guards! Guards!, Errol and the (female) Noble Dragon technically qualify; they may both be dragons, but they are of different species (draco vulgaris and draco nobilis, respectively).
In Witches Abroad, Greebo is strongly implied to have had sex with a drunken noblewoman at the masqued ball. Greebo is a cat, albeit in human form at the time. (Granted, Greebo is infamous for raping anything four-legged and female up to and including a bear ... but this time, the noblewoman evidently cooperated.)
Many of the girls in Harry's year are fond of Firenze, but he, of course, does not return their feelings.
Hagrid's parents were a human wizard and a giantess. Their relationship didn't seem to last very long, as his mother left when Hagrid was very young.
There's also Fleur, who has a veela grandmother and who marries full-blooded human Bill.
Quasi-example: Nymphadora Tonks and Remus Lupin (werewolf). "Quasi-" because being a werewolf is not hereditary in this universe, being transmitted by bites (it serves as an HIV allegory), but they're still treated as a separate species in-universe and bigots still refer to their (very rare) offspring as "half-bloods".
Teased in The Demon Awakens, the first of R. A. Salvatore's novels set in his own world of Corona. A centaur comments that he'd only let a woman ride him - and only if he got a ride himself afterwards.
Subverted slightly in Wild Cards wherein there was a human/centaur sexual relationship. The subversion comes from the fact that Finn the Centaur was once entirely human, but the Wild Card virus turned him into a centaur. Brain Trust/Tachyon [human/Takisian], plus Tachyon also had many other relationships with human women, including one which resulted in Half-Human Hybrid child (mentioned as deceased) and grandchild. Popinjay also had a Takisian wife. Then again, Takisians are essentially human.
The most prominent are Gavin (Human) and Asyr (Bothan), who catch quite a lot of flak for their romance, what with them being war heroes and all. Interestingly, it's the Bothan who catches most of this—even though a prominent Bothan politician notes to her that xenophilia isn't unknown among Bothans. It's just that she wants to stay together long term and adopt children - the parts match up, but they can't reproduce.
One of the more memorable examples, played for bittersweet laughs and occurring off-screen in the past, was the romance between Corran Horn (Human) and Chertyl Ruluwoor, a sterile Selonian (an alien species resembling giant, anthropomorphic eusocial otters). On a personal level, they were really compatible — however, other factors meant they couldn't be together. Corran wanted kids, and Chertyl was biologically incapable of having them. More importantly, a quirk of Corran's bio-chemistry made his sweat acidic enough to penetrate the waterproof fur of his Selonian lover and irritate her skin, while her fur had a similar effect on his own; they effectively sunburned each other whenever they touched.
Because of this experience, Corran also leads into the discussion with pointing out that if one does contemplate dating across species lines, one is obligated to do the research, as things could turn out even worse than intraspecies dating. After all, it's one thing if you or your partner) want kids and your respective species are biologically incapable of it — it's another thing entirely if one of the species has biological or cultural traits that could complicate or even accidentally end a relationship. The examples he gives includes a species being prone to giving love-bites during sex... with ten-inch fangs. That's really something you'd be behooved to learn before the fact. The unspoken message of the lecture is that interspecies relationships can work, but it takes a lot of work.
The Wraith Squadron books had a fair share of this, too, with two of the squadron members — one Human, one Twi'lek (the woman, naturally) - getting together
In the Rogue Squadron books, there's also a male Twi'lek, Nawar'aven, hooking up with a female human. This being written by Stackpole, it's completely out of focus.
Among the Wraiths, the team plays a prank and allows the residents of a seedy bar to think that Piggy (the male Gammorrean, who looks like exactly what you'd expect from the name) and Falynn, a human female, are a couple. They're not, and Piggy gently takes her to task for being embarrassed about being seen with him.
Shadows of the Empire also had Xizor attracted to and trying to seduce Leia. Xizor is a Falleen, a suspiciously mammalian-looking "reptilian" species (EU sources have since retconned them to be "reptomammals") whose members can (and do) produce pheromones that can ensnare a good chunk of the sentient species in the Galaxy.
"One Last Night in the Mos Eisley Cantina" stars the humanoid wolf and the giant lamprey-thing, who are given the identities of Lak Sivrak and Dice Ibegon, a male Shistavanen and a female Florn Lamproid, two alien predators who are very much in love with each other and find great physical pleasure in their union. Tragically, Dice is killed in the Battle of Hoth, but as she dies in Laks arms, she implores him to believe in the Force and keep fighting. Lak (Who drowns in loneliness) later fights in the Battle of Endor and his X-Wing is shot doen. As he falls to his death he has a vision where he first meet Dice who's offering him the chance to "Leave the cantina alone" and be alone in death, or "embrace her" again. He chooses the later and in the end, both become force ghosts.
"Nightlily: The Lover's Tail" explains that the goatman (Feltipern Trevagg, a male Gotal) and the yam-nosed reptilian (M'iiyoom Onith, a female H'nemthe) are dating when we see them in the film, and that Feltipern drugs M'iiyoom that evening in order to get her into bed. This story emphasizes the lesson from "Wedge's Gambit" about the importance of studying up on other races if you're into dating outside your species with its Twist Ending: H'nemthe females are culturally indoctrinated to eviscerate and partially devour their lovers after sex, as a response to the overwhelming majority of males in the species, and as they see this as an act of love, Feltipern's empathic abilities didn't warn him before she ate him. Classifies as Laser-Guided Karma since he did essentially Date Rape her, after all, and was planning on just wooing her and then abandoning her after a night of passion.
There are numerous species that are classified as "Near Human". Which basically means by the proper definition of the word, they're not really separate species at all, just humans with minor visual differences (and occasionally a bit more, like the Miraluka, who have no eyes and see through the Force-and who have a couple of cases of this trope themselves. The birth is usually difficult, though). Given the vast amount of time covered in the EU, it's likely that all the "Near Humans" were descended from regular humans at some point in the distant past. On the other hand, the EU also includes a few romances between humans and distinctly non-human aliens, where it's made clear that they're not capable of reproducing at all.
Death Star has two sets. One pairing has no humans in it; it's a Twi'lek woman - who has blue skin and brain tails - and a Zelosian man, a Plant Alien who looks like a human with green eyes and blood. The other pairing looks human, but one of them is actually a Mirialan, an offshoot of humanity.
In The Crystal Star, Han Solo met a female Ghostling, a species that is considered, by humans at least, to be incredibly beautiful and apparently most ghostlings feel the same about humans. The problem is that Ghostlings evolved on a low-gravity planet with almost no physical hardships or predators and are extremely fragile by human standards. According to Han any relationship between a human and a ghostling inevitably ends with the ghostling's death. Light touches cause serious bruises to them and even a minor impact can kill.
For Galaxy of Fear, the reason the shapeshifter alien Hoole is considered the uncle to human Tash and Zak Arranda is because his brother Moloch married their aunt Beryl.
Star Trek: Titan has the husband and wife team of Will Riker and Deanna Troi (Human x Half-human Betazoid). Troi is herself the product of an Interspecies Romance (Human x Betazoid) and has a half-brother who is a Betazoid-Tavnian hybrid.
Piro and Ibronka in The Viscount of Adrilankha. Granted, this one is less obvious due to the characters being of different clans of the same race which were manipulated by extradimensional aliens millions of years in the past to be almost the same but have a few traits resembling the native wildlife of the world instead of actual different species, but the severity of the cultural taboos make this count. There are also Zerika and Laszlo, who are Dragaeran and Easterner, respectively.
Being based on a Dungeons & Dragons world (see below), there was a surprising amount of angst from Drizzt about his eventual romance with Catti-brie — though admittedly only part of that was due to race. It's done with now, and they're married, though Salvatore has said he's not gonna give them kids.
It might have had something to do with the fact that he knew her when she was ten years old...and that he's pushing eighty but would live for centuries (barring accident, violence, or disease).
The angst was also partially, at least at first, about the part where Cattie-Brie was the love interest of Drizzt's best student Wulfgar before he had a bridgecavern dropped on him when Drizzt became more popular.
Contrast him with Jarlaxle, the charmingly evil dark elf rogue, who can and will sleep with anything with two legs, a pulse, and the ability to consent (which is what makes him charminglyevil, not just evil). And maybe female sexual organs. He and Drizzt both are noted to be unusual among drow males, who are culturally xenophobic. (Females will sleep with anything, including demons, in the pursuit of power, though there's probably no romance. For that matter, intraracial relations in traditional/Llothian Drow society are rarely all that romantic.)
There's a reason behind the old joke "How the Drow do it? He lies on his back, she stabs him with a dagger, as a sacrifice to Lloth".
Then again, Forgotten Realms got Crinti (aka "Shadow Amazons"), descendants of southern drow, humans, and half- (surface) elves who looks accordingly and got strong drow cultural influences. The people numerous and strong enough to raid every once in a while Halruaa, of all places.
In The Legend of Huma, the silver dragon Gwynyth falls in love with Huma, romancing him in the form of an elven female. Once she reveals to him her ruse, he's surprisingly ok with it. It turns from one interspecies romance into another.
During the War of the Lance, Gilthanas falls in love with Silvara who unbeknownst to him was Gwynyth's sister. Like Huma, he assumed she was elven. When her nature was revealed, he didn't take it nearly as well.
Tobias and Rachel have this — Tobias is a Human stuck in the body of a hawk who regains the ability to temporarily turn back into a human. At least one of the books directly addresses the ambivalence both feel about the relationship, including with issues such as Tobias's much shorter lifespan if he stays as a hawk.
In addition, Andalites (a centauroid alien species) can use their morphing "technology" to change themselvespermanently into another species, and two are known to have done so:
The above Tobias's parents were a Human and an Andalite (Ax's elder brother Elfangor, in fact), and their romance is depicted in The Andalite Chronicles. And as their kid is sort-of half-andalite, his relationship with Rachel is interspecies regardless.
In The Hork-Bajir Chronicles, the Andalite Aldrea became Hork-Bajir and married the Hork-Bajir seer Dak Hamee. Her rejection of her own kind was partly motivated by horror when the Andalite war-prince Alloran tried to genocide the entire Hork-Bajir species.
In Robin Jarvis' The Oaken Throne, a prequel to his Deptford Mice trilogy, a war is being waged between the bats and the squirrels. In the midst of this, a squirrel princess named Ysabelle and a bat named Vespertilio fall in love.
Averted in Goddess by Mistake, a light fantasy novel wherein the heroine finds herself in an arranged marriage to a centaur (who takes human shape for the actual coupling).
Vorkosigan Saga: Miles Vorkosigan's on-again/off-again relationship with Taura should count (despite the Absent Aliens setting in the series, she is at least as far from Human as a Drow is). Leo Graf's and Bel Thorne's respective marriages into Quaddie society also apply.
In Holly Black's Valiant, Val, a human, is in love with Ravus, a troll.
Whose own father was a human, although apparently troll blood always breeds true.
Magician: Tomas and Aglaranna (human / elf), plus Nakor and the Dark Queen (she's human, but it's strongly implied that he's not).
Tomas was somewhat mutated by being possessed by the Valheru Ashen-Shugar, a survivor of the race who used to own the elves. He stated that his lifespan had been extended to a thousand years.
Tristran's parents, Una and Dunstan (faerie / human), obviously. And a side mention of an ordinary cat being knocked up by a faerie cat, producing a smoky blue kitten with color-changing eyes. The other kittens in the same litter were normal, but cats can have kittens by multiple fathers in the same litter.
Robert Silverberg's short story Ishmael in Love is told from the perspective of a dolphin in love with his (human) trainer.
The product of Nira and Jora'h's interspecies romance (and her half-siblings, some of whom are also her cousins, born of the interspecies rape of Nira by Jora'h's brother among others) save the galaxy in Kevin J Anderson's Saga of Seven Suns.
Interspecies romance was fairly common and accepted in Alien Nation, although the Tenctonese tended to be fairly rough in sex so had to visit clinics to make sure they took it easy on their human partners. One of the continuation novels explores the idea of Newcomers and humans interbreeding, but it turns out to be a deformed Tectonese girl produced from an experiment who was mistaken for being half-human for a while due to her single heart and other weaknesses.
Spider Robinson handles interspecies romance quite logically in "The Blacksmith's Tale" in his Callahan's Place series.
Mickey Finn (A 6'11'' tall, 600 pound robot/cyborg alien) "You do not even know if we are sexually compatible—"
Mary Callahan (Human) "The hell I don't. I can see fingers and a tongue from here; anything else is gravy."
The Firekeeper series presents us with the namesake heroine, Firekeeper, and Blind Seer, a Royal Wolf (bigger than most and possessing a sentient mind). Firekeeper wrestles with these feelings for a while but seems to come to terms with them by the end of the sixth book.
Commander Bradshaw of the Thursday Next books is married to Melanie, who's a quite nice woman with conservative taste in dresses, and who also happens to be a six-foot-something gorilla. Bradshaw is rather sensitive about the topic.
In the Nursery Crime books by the same author, Ashley, an alien member of the force (who at one point mentions that the type of earth creature his species most resembles are several jellyfish stuffed inside a balloon too small for them) becomes quite taken with Mary, and even manages to take her out on a date that she tries fairly hard to avoid. The end result is oddly sweet.
There's a lot of this in the Twilight books, especially concerning Bella.
We also have a multiple-case scenario here, if you remember that:
1) Edward is (up to some point) a living corpse (making Bella suffer from a severe case of Necrophilia in the 4th book and there after)
2) Edward is 117 years old (making him 100 years older than Bella, who is a 17 year old girl at least on the first 3 books).
Though by the end of the series, Bella is a vampire too, so this no longer applies to her and Edward. But then we're told that there's going to be a future romance between their half-vampire, half-human daughter and shapeshifter-previously-thought-to-be-werewolf Jacob.
Many of Tom Holt's books feature a character who is really a type of magical being shapeshifted into human form, who fancies a certain human.
In Nothing but Blue Skies, the protagonist is a female dragon disguised as a human, who develops a crush on a young human man.
The J.W. Wells & Co. series features a she-goblin who shapeshifts into a different beautiful human girl every day and tries to hit on the main character. She mentions that lots of goblin girls like to have flings with humans, and that as shapeshifters, they are open-minded and don't care much about appearances.
Djinn Rummy feature a genie who very reluctantly finds himself falling for a human.
In J. R. R. Tolkien's Middle-earth legendarium (The Lord of the Rings, The Silmarillion, etc.) there are several known cases of romances between elves and humans, elves and half-elves, and half-elves and humans: Aegnor/Andreth (unhappy Star-Crossed Lovers), Lúthien/Beren (happily married), Nimloth/Dior (happily married), Finduilas/Túrin (unrequited), Idril/Tuor (happily married), Elros/his unidentified human wife (happily married), Mithrellas/Imrazôr (married until she walked out), their son Galador/his human wife (married), Celebrían/Elrond (happily married), and their daughter Arwen/Aragorn (happily married)* A short passage in The Hobbit suggests that someone in the Took family tree had married into a "fairy" or elven family, which is given as a possible reason for certain hobbits being far more adventurous than the majority. But this is almost certainly a leftover artifact from before The Hobbit was dragged into the Middle-earth stories, in which "fairy" means nothing and such a legend would be far more than an inconsequential factoid.. However, Tolkien pointed out in a letter that elves and mortal humans (which include hobbits) must be the same biological species to produce fertile offspring, so the above don't truly count. What do count:
Melian, a Maia (angel) and Thingol, an elven king. They married and even had a daughter (the above Lúthien), thanks to angelic Voluntary Shapeshifting and Melian giving herself an actual flesh-and-blood body.
Tom Bombadil, an ambiguous "eldest" something, and Goldberry, some sort of river nymph. It's unclear what, exactly, Tom Bombadil is, but chances are he's not a nymph. Doesn't really matter for the story, though, especially if we consider that they are both definitely spirits in human form.
It is said that Wargs and Dragons are the demimortal offspring of the demonic Umaiar who chose specific forms to reproduce with mere animals. In the same way that Ungoliant mated with normal giant spiders and brought to the world her monstrous yet mortal spawn, like Shelob. If one thinks about it, Luthien's mother is of the same supernatural species as those demons, and the big differences are on the father's side.
Happens in Amelia Atwater-Rhodes's novels, particularly in Hawksong, the first novel of her Kiesha'ra series. To prevent war, an Avian (bird shapeshifter) princess and a Serpiente (snake) prince consent to a political marriage to end their generations-long war, but find themselves falling in love. Their child, a wyvern who represents both her parents' shapeshifting powers, in turn chooses neither an avian nor a serpiente mate, but a wolf woman. This is a good thing as choosing any male mate would lead to her combined powers manifesting very strongly and dangerously in any child she bears.
In her modern day, Nyeusigrube books there are several interspecies romances between vampires, shapeshifters, humans, and sometimes witches, but none are so unusual as Shevaun and Adjila. Shevaun is a vampire and Adjila is a Triste, a particular kind of witch whose blood is almost always poisonous to a vampire. The two species are usually sworn enemies to a point that Triste can be a synonym for vampire hunter. They have been partners for centuries.
The main characters in "The Owl and the Pussycat". (And in the incomplete, post-posthumously published sequel, they have kids. But this is Edward Lear.)
The Dresden Files has a Werewolf/Wolfwere pairing and a human/vampire pairing. A couple was split up when it became a wizard/half-vampire pair. Summer Knight has four changelings, the results of human/fae pairings, although the only background we're told about suggests there's not much romance involved.
And let's not forget the other wizard/vampire pairing in the series: Margaret LeFay and Lord Raith, the parents of Thomas Raith...who's Harry Dresden's older half-brother.
In Cold Days it is revealed twins Sarissa and Maeve, daughters of Mab, were Changlings early in their life as well. Meaning their parentage was a Fae/mortal.
Somewhat amusingly (and not altogether intentionally) there's a wizard/fallen angel pairing in Skin Game. It turns out that the very "intimate," if altogether not carnal, situation of Lasciel's shadow living in Harry's mind made him pregnant with their child - a spirit of intellect, which is apparently what happens in cases like this.
In Radiance by Grace Draven, Ildiko is a noblewoman from the Gauri kingdom and enters an Arranged Marriage with Brishen, prince of the Kai who would resemble a human if not for his grey skin, sharp teeth and glowing eyes and the fact that his species used To Serve Man.
Artemis Fowl plays with this trope in Book 6, when Holly and Artemis kiss and start developing romantic feelings for each other. The rest of the book sees their friendship go through a lot of rough territory thanks to Artemis's machinations but by the end its left ambiguous.
Continued in The Atlantis Complex where said mental disorder caused Artemis to have "Orion", a split personality who constantly proclaims declarations of love to Holly. Orion even hints to her that Artemis also has similar feelings towards her but chooses to hide them. It's borderline Unresolved Sexual Tension now.
Played straight with Turnaball Root and his human wife Leonor. In fact, the fact Leonor is dying is what causes many events in The Atlantis Complex.
The Legend of Little Fur has this as a constant mystery until A Riddle of Green- Little Fur is half elf, half troll. Everyone wonders how an elf and a troll could love each other enough to have a child. The answer: since Little Fur was going to save the world, a she-wizard captured an elf and a troll and kept them locked up together until they loved each other enough, and then she released them once Little Fur's mother was pregnant.
In Diane Duane's The Tale of the Five series, the first human protagonist gets involved with a fire elemental, while the second takes up with a dragon. Sex definitely does happen, though it tends to be a complicated sort of out-of-body experience.
In the Courts of the Crimson Kings, by S.M. Stirling. After he saves her life, Martian Action Girl Teyud matter-of-a-factly takes Adventurer Archaeologist Jeremy off to her cabin. His human co-worker looks ready to protest (to which Jeremy responds with a big grin and The Bird) but doesn't say anything till afterwards; her main objection being that a bust-up between the two — likely given the cultural differences between Earth and Mars — might endanger their mission. A Martian doctor who examines Jeremy later seems rather squicked out by the idea of having sex with a human, even as a simple matter of recreation.
In Codex Alera, main character Tavi has tense partnership-turned friendship-turned romance with Proud Warrior Race Girl Kitai. He's human, she's a Marat (basically human, but with enough differences to qualify as a seperate species- white hair, abnormally high body temperature, excellent night vision, and the ability to bond telepathically with animals being chief among them). The animal she bonds with: Tavi. She really wanted a horse though.
Referenced in-verse. Many humans believe that Marat mate with their totem animals. When someone asks Kitai if Doroga (her father) mates with his gargant Walker (think giant badger), Kitai responds "Of course not. Walker would never stand for it".
In Elizabeth Kerner's Song in the Silence series, we have Lanen (human) end up with Ahkor/Varien (dragon). This is facilitated by divine intervention, as Ahkor is changed into human form after he is grievously wounded in the first book. It becomes a plot point later on when Lanen ends up pregnant. While Varien's shape is human, his blood is apparently not, and the mixture of the two in the kids is slowly killing Lanen before they get some mages to fix it. Later on both Varien and the kids get the ability to shapeshift between forms at will.
Metaplanetary by Tony Daniels (not to be confused with Metaplanetary by S. P. Meeks) pairs a human with an "emancipated" software program. Their kids exist partially in the "real" world and partially in cyberspace simultaneously, and it's mentioned offhandedly that their baby talk was white noise. (There's a Handwave about radiation—just go with it.) The intelligent ferret also has a powerful sex drive, which turns towards humans when her original body dies and she winds upSharing a Body with an Artificial Human, but she's after Anything That Moves, in a rather blunt fashion. (Yes, this book is weird.)
Played straight and taken seriously in Ann C. Crispin's Voices of Chaos, where the human female and cat-alien male leads end up in a romantic (and sexual) relationship. Really, considering that it's set in a series whose premise is fostering interspecies understanding and universal goodwill among a cooperative league of friendly alien nations, the only surprise is that it took until the sixth book to do it.
In the Mercy Thompson novels, werewolf males typically marry human females. This is because few women opt to become werewolves (or survive the process of becoming one), and because female werewolves in this series almost always miscarry during their change, making them unsuitable mates for males who want to be fathers. Mercy (a coyote shapeshifter) was once courted by a werewolf, who'd sought a fertile mate with similar powers.
Mercy herself is the product of a one-night stand between her human mother and a Native American coyote shapeshifter.
In the Foreigner novels, we have Bren and Jago his bodyguard sleeping together. Needless to say this was a huge scandal and most just pretend they aren't.
Aly and Nawat from Daughter of the Lioness. She's human, he's a crow, but crows in the Tortall Universe can shapeshift into humans if they want. The short story "Nawat" follows up on the difficulties that arise from this.
In Julie Czerneda's Species Imperative trilogy, lampshaded and subverted; one of the alien characters has as his Running Gag happily and frequently teasing the main character, a human woman, about human fictional tendencies in this regard, jokingly accusing her of seeking this very trope, and happily telling her that his species has "No external genitalia". At one point, when he is sleeping, she is tempted to check.
Czerneda, a biologist by education, tends to give her alien species differing reproductive systems and/or genitalia.
The Belgariad has Belgarath and Poledra (human/wolf, albeit a wolf that is also a sorceress and can take human form), who produced twin daughters Polgara and Beldaran. As well, the Dryads are a One-Gender Race and reproduce with human men. Ce'Nedra is a Dryad and the wife of Belgarion, the hero. Belgarion is a distant descendant of Beldaran.
The Darkest Powers series has Chloe Saunders and Derek Souza, the latter of whom is a werewolf. True, Chloe is a Necromancer, but for all intents and purposes, she is human.
The protagonist of the Garrett, P.I. series has slept with pretty much everything good-looking, humanoid and female, from half-fairy to ghost to demigoddess to space alien ("silver elves"), although he always comes back to Tinne Tate (basically human, perhaps with a bit of elf and/or dwarf blood) in the end. What few species Garrett hasn't bedded, his associate Morley probably has.
Subverted in Spar, a 2009 short story by Kij Johnson. After the destruction of her spacecraft, a human woman is trapped in a lifeboat with a Starfish Alien survivor, and they have squick-inducing sex simply because there's nothing else to do. Worse, she has no means of communicating with the alien, so never discovers if the act has any meaning for it; or even if she's having sex with a sentient alien at all and not just their equivalent of the houseplant.
The same author first gained renown with an award-winning 1993 short story, "Fox Magic" about a romance between a Kitsune and a human, which she later adapted into a novel.
In the 1922 novella Lady Into Fox, a British nobleman's wife mysteriously turns into a fox (it's never revealed why), but they continue to live together until she leaves him, because of her now-wild nature. However, she later returns with her children and fox-mate, and they all live together with her ex-husband until she gets killed during a fox hunt and the rest of her family scatter.
Also subverted in the short story "And I Woke and Found Me Here on the Cold Hill's Side" by James Tiptree — humans are driven to have sex with the new and unusual, but in the end receive nothing from the experience except abuse and abandonment.
Art and Myrtle Mumby in Philip Reeve's Larklight books are a product of this, to an extent - their mother is a Shaper in a biologically human body, but it's implied that a few things bleed through (like Myrtle's talent for alchemy). Averted with Jack and Ssilissa - only ever one-sided to begin with, and pretty much completely dropped once Myrtle shows up.
During The Adventures of Fox Tayle, Fox is helped along on his journey escaping the lab where he was created and the FBI by a handful of sympathetic humans, including Wanda and Diana. Nothing too serious happens, though.
In Sharyn McCrumb's mystery novel If I'd Killed Him When I Met Him, Miri Malone, who teaches art at a college and creates art with bathtub toys, hires a lawyer so that she'll be allowed to legally marry a dolphin. The lawsuit never gets anywhere, as she decides on a pre-conjugal visit to the dolphin's tank. This proves to be a very bad idea. Dolphins will voluntarily mate with practically anything. They also mate underwater.
Mostly played straight in John Varley's Gaea Trilogy, with the Titanide species in particular being (literally!) custom-built for Hot Skitty-on-Wailord Action. Subverted with the Supra variety of angels, which offer sex to human guests as cultural protocol but don't take it any further than a courtship dance and ritualized faux-copulation.
Several examples appear in the Mithgar fantasy series. There are several pairings that a reader would somewhat expect (Elf/Human, Mage/Elf) but some others are a bit more suprising:
A Dwarf/Human romance is at one point treated as much more taboo than others (largely due to the Dwarves' strong sense of pride in their race).
One sex addicted human Queen (who was well known for having her lovers executed as soon as they started to bore her) was rumored to have taken a horse to her bed.
While Human/Elf pairings aren't taboo, they are generally treated as a bad idea and very tragic due to the human's mortality and the couple's inability to have children. After a somewhat angsty Human/Elf romance is finally consummated the female Elf gets pregnant. Turns out the father isn't a Human, he's actually a Human/Mage/Demon hybrid, making their child half Elf, quarter Human, one eighth Mage and one eighth Demon. This also gives the father the benefit of immortality due to his non-Human heritage. The child's exteremely diverse genetics are an important plot point in a later novel.
Interestingly it is highly suggested that Chakkia, the female Dwarves, are actually a different species than the Chak (male Dwarves). The Chakkia are never described and rarely seen because they are jealously guarded by the Chak. They never leave the Dwarvenholts and are always veiled when out of their personal quarters. Besides intensely different builds and grace, the <light> of Chakkia seen by Mages is so different that one specifically believes they must be a different species. In another novel a seer recognizes what the Chakkia are, but never specifies it. One book even has a scene from a Chakkia's perspective which included thoughts about what the secret the Chak didn't know about them was. Word of God is that he's not going to explain it.
Finally an example that technically isn't Interspecies, but is mostly treated that way in-Universe due to lack of Dracobiology classes: Dragons are exclusively male. They mate (once every 5000 years) with Kraken, meeting at a large whirlpool. After competing for rights, the Dragons throw themselves into the waiting embrace of a Kraken appearing in the whirlpool, going in order from strongest to weakest. The Dragon and Kraken then mate underwater, sometimes resulting in the drowning of the Dragon. The offspring are sea serpents which live several thousand years before a metamorphosis into a Dragon or Kraken depending on gender. Most characters have no clue that the three monsters are the same species.
Olaf Stapledon's Sirius, about a man who creates a super-intelligent dog. Of course turns out badly in the end.
A minor yet important aspect of the Sholan Alliance series. Though there it's less "romance" as it is "irresistible urge to have sex between permanently bonded telepathically linked couples". This even allows for the production of hybrid offspring, between both male Sholan/female human couples and between male human/female Sholan couples. Sholans are basically Cat Folk.
Dragons in Our Midst has this in spades, as a major plot point is that several dragons were disguised as humans and took on human spouses.
Ultimately the case in John Collier's humorous novel His Monkey Wife which is sort of like Jane Eyre if Jane was a sapient chimpanzee.
In The War Gods series by David Weber there are 5 races of man, Human, elf, dwarf, hafling and Hradani (filling the role of orcs). All of them can interbreed, but many of the resulting children are sterile. However, each race evolved from baseline humanity in different ways. Hradani and dwarf are more or less true evolutions and are biologic changes to how they tap the magic field. (Both live longer at the cost of reduced fertility and ability to do magic or psonics while dwarves get rock shaping skills and Hdrani become bigger and stronger and are more able to use the magic field to supplement their strength). Haflings are pretty much mutants caused by the last wizard war. Elves though were not part of a subrace as such until the original wizard war ended and secondary casters whose powers are innate and didn't require extensive training to unlock were found to be too dangerous to have their power. They agreed to under go a spell to change how their set of genes tap the magic field so that they lose their magic but gain immortality. As such half-elves are non-sterile, live 400 years, and there is an entire nation run by half elves calling themselves the purple lords. If a half elf breeds with an elf or another half elf, the children are half elves, but if they breed with a human their children are just slightly longer lived than most humans. Elf-dwarf is mentioned as a very sad affair. Half dwarves are non sterile and resulting in alot of mixing with the empire of the axe having dwarves with more than a bit of human blood (resulting in folks having most of the dwarven skills but little shaping abilities) and humans that are a bit shorter than normal due to dwarf blood. Human-Hradani hasn't been seen in ages, but Wencit testifies it's very good they are sterile. Like all half humans they have the potential for wizardry or psonics, at the same time they have the Hradani ability to tap the magic field, resulting in a far higher number of powerful wizards being half Hradani. It's hinted that wild wizardy may be connected to the Hradani ability.
There are distinct shades of this in Dinoverse, in which middle-school children have their minds cast back in time into the bodies of prehistoric reptiles, mostly dinosaurs. The natives are more intelligent than you'd expect, and everyone appears to be the same species, but these are still dinosaurs with kids' minds and actual local dinosaurs.
In the first book/two books, a group of Leptoceratops want Canadayce to run away from the Tyrannosaur and join them, Janine quickly becomes close with a native Quetzalcoatlus she calls Loki and half-seriously considers him her 'first boyfriend', and Bertram meets an Ankylosaur who'd just lost her mate and immediately latches on to him, an affection he finds himself returning. These are fairly innocent and for the most part can be interpreted as sudden friendship. Certainly they don't have too much trouble when leaving their new friends to go home. Canadayce "kisses" Bertram, but perhaps because they're incompatible species at the time this does nothing; they kiss more successfully when both are human again.
The next books have Patience and an Acrocanthosaurus she names Green Knight. He actively courts her, even presenting her with shiny gifts and nuzzling her at length. When Patience taps into her host body's mind she sees that her host had courted him and pined after him to no avail - he's interested in Patience. Unlike the previous kids, she earnestly falls for him, too, and is devastated when he dies, despondent even when back in her human body and proper time. When it turns out that he's somehow Sharing a Body with one of the other returned kids, they immediately strike the relationship back up. GK's feelings leak over into his human host's mind, so somehow all three are okay with this new situation.
In Kurd Laßwitz's early science-fiction novel Auf zwei Planeten (On Two Planets, 1897), German scientist Josef Saltner is taught the Martians' language by the pretty La. They become man and wife.
In Thorne Smith's 1931 novel The Night Life of the Gods, inventor Hunter Hawk falls in love with 900-year-old woodsprite Megaera.
In The Uplift War there is a (partially symbolic) marriage between Robert, son of the (human) governor of Garth and Athaclena, the Tymbrimi ambassador's daughter, though they mostly did it to solidify their species's alliance and both expect to find mates of their own species later. Partly due to the Tymbrimi's extremely humanoid appearance, Robert was seriously attracted to Athaclena for a while, though she deconstructed this trope by pointing out that it wouldn't actually work between them, let alone result in offspring.
Male neo-dolphins have a tendency to hit on human women. Sa'ot, for example, in Startide Rising.
Interspecies marriage is oddly invoked in Infinity's Shore, when the human Rety rescues a male urs from being eaten by carrying him in her tote bag. Female urs carry their (much tinier) husbands in their pouches, so yee decides Rety is now his wife. She seems fine with that, but it isn't clear whether or not he's actually become attracted to her.
½ Prince has a romance between a phoenix and a talkingmeatbun!
His character C'mell is also a cat, but she's a genetically-engineered Underperson, in human form, and specifically bred to look attractive to humans. Her job involves seducing VIP visitors in order to learn their secrets, but any actual consummation is forbidden. In "the Ballad of Lost C'mell" she actually falls in love with the human Lord Jestocost, but he's too focused on justice to show affection to anyone. In Norstrilia she escorts the human protagonist Rod McBan, who's disguised as a cat-person for security, and points out that if they had sex nobody would be any the wiser. However, she seems relieved when he refuses As a boon, E'telikeli grants them a dream where he spends a thousand years as her cat-man husband.
In Taylor Anderson's Destroyermen series, it is often hinted and implied that Gunners Mate Dennis Silva and one of the Lemurians, anthropomorphic cat-lemur hybrids, is involved in a relationship. While sexual relations are implied, they are never confirmed.
In the fifth book, Walker's Executive officer asks the engineering officer Spanky if he will get in a relationship with a specific Lemurian, referring to it as "going Silva." According to the omniscient narrator, this phrase has become common slang for the humans whenever referring to an inter-species romance with a Lemurian.
In the second book a Lemurian Blas-Ma-Ar, also known as "Blossom" is raped by a human Destroyermen.
Throughout the series, particularly in the first three books, it is shown that the humans are sexually attracted to the lemurian females due to having similar proportions in the relevant areas and a looser sense of modesty than humans. While this largely occurs because there is a lack of human females, the attraction is still noted.
Enchantress from the Stars has Elana, a girl from The Federation, an extremely advanced society, fall in love with Georyn, a young man from a planet stuck in Middle Ages. This is more justified than many examples, as Their species are extremely similar to the point that Elana is mistaken for a native. However, neither of them could be happy in another world, so they part once the Federation's expedition departs.
Mostly averted in James White's Sector General novels, in which inter-species romance is barely even mentioned, because all of the different sentient races are so biologically different, to the point of potentially not even having mutually comprehensible concepts of love, romance, and sex. Early novels even suggested that interspecies sexual attraction was viewed as a mental illness, which was dropped later on, probably out of fear that it would be viewed as a metaphorically racist insult to real-world inter-racial relationships. Very late in the series, it's revealed that a major character has in fact formed a romantic relationship with a non-humanoid being, although in very peculiar and unique circumstances.
Oscar Wilde's short story "The Fisherman and His Soul" has a Tall, Dark, and Handsome Fisherman who catches a cute little mermaid in his fishing nets, and releases her when she promises to sing every day so he can catch more fish. Within a few days he falls head over heels in love, and while she likes him back a lot as well, she can't accept his feelings because he has a soul, unlike non-humans like her. And so the young Fisherman begins to work on getting rid of his own soul, succeeding and getting together with her... Towards the end, however, the mermaid dies and her corpse washes ashore, and the heartbroken Fisherman pretty much drowns himself as he holds her lifeless body.
The furry erotic novel A Fox Tail has Vulpie (fox, duh) and Polar (wolf). In universe it's not uncommon for male wolves to find vixens attractive but most religions consider it an abomination, and Vulpie and Polar take it a step further by being gay as well.
The children's story The Wainscott Weasel includes a male weasel who falls in love with a female striped bass. At the end, the fish has to say good-bye because humans are cutting out the pond to the ocean to drain it, meaning that she will be carried out to sea.
The relationship between Jago and Bren in the Foreigner series counts as this. Because of the social, emotional and psychological differences between the Atevi aliens and humans you can't really call it a romance, but they make sure that all emotional and physical needs are met in their relationship. Besides that, one of the main themes in the series is the difference in psychology and emotional wiring between the two species, and the slow build of their relationship is a very sweet in-universe example of how difficult the interface between the two species can be.
In Dean Koontz's urban fantasy mystery The Haunted Earth interspecies relationships between humans, mythological beings, aliens, and alien mythological beings are both possible and potentially fertile. The main protagonist's partner is a canine demon (or ex-demon) who has an open relationship with their secretary.
Rats, Bats and Vats: Ariel the rattess NCO has romantic feelings for her former human commander, Major Fitzurgh, forged by their teamwork on the frontlines together. Though they have to keep things platonic — not necessarily because Bestiality Is Depraved, but more because she's small enough to fit into his pocket — they are still quite devoted to each other. When she gets transferred into a human body via Brain Uploading, she wastes little time in jumping him.
Dragon's Ring, also by Dave Freer, has Meb (a human) who slowly develops feelings for Fionn (a dragon), which are somewhat reprocated. Due to the fact that dragons can shape change though, with Fionn taking a human form when he's around Meb, she remains unaware of the fact that he's a dragon for a healthy chunk of the book. Even when the fact is revealed, Meb's pretty alright with the whole idea.
The Moreau Series provides several examples of romances between various types of anthropomorphic 'Moreaus', as well as one between a moreau and a human. In the Apotheosis series, which takes place centuries later in the  same universe, Nickolai Rajastan is maimed and exiled for having an affair with a panthress, as interspecies relationships are forbidden by the religion of St Rajastan, his ancestor.
In Wen Spencer's Ukiah Oregon series Ukiah's relationship with Indigo and Atticus' relationship with Ru are this, as Ontongard Breeders aren't technically human, but since they're Human Aliens it's not obvious to bystanders. The fact that both relationships are interracial has caused them a bit of difficulty, though. (Atticus and Ukiah are half Cayuse, half alien, Indigo Zheng is Russian/Chinese, and Hikaru Takahashi is Japanese-American)
In Storyteller, Loquastro, the mynah bird falls in love with the fish princess Artemisia. The only reason why couldn't be together is obviously because Loquastro can't swim and Artemisia can't breath air.
in Seeker Bears, Ujurak (a grizzly bear) has attracted the attention of Sally (a human), who is helping other people clean up animals from the oil spill. They even hold hands at one point...but then Ujurak turns into a bear in front of her.
Toklo also feels temporarily attracted to Tikkani, a female polar bear. Bonus points for grizzly bears and polar bears seldomly having cubs together.
In the short story Snowmaiden a human starship saves a young woman of an unknown Human Alien species from a starship wreckage. She and the doctor taking care of her quickly fall in love. Their problem? She lives at temperatures far below zero, room temperature would kill her. And they don't even speak each other's languages — The Federation hasn't contacted her species yet. The title — her nickname — alludes to a 19th century play and an opera about a snow girl who fell in love with a human but ended up melted by sunlight. The story ends with a bittersweet goodbye on her home planet. Then they finally dare to touch each other without glass between them (she pulled his hand). She ends with a second degree burn on her cheek, he gets a superficial frostbite of his palm. Thus they get something to remember each other.
Thumbelina defies the trope, courtesy of Thumbelina herself, who is wooed by a toad, a scarabee and finally a mole. She narrowly escapes all of them. She gets closer to playing it straight with the swallow, who actually pines for her, as she goes off to marry a fairy prince - which, it turns out, is as close as Thumbelina gets to someone of her own species.
In Even the Wingless the Slave Queen, a shapeshifting dragon-like alien, finds herself falling for Lisinthir, a Space Elf and ambassador from a multi-species Alliance that males of her species have been raiding for sex slaves. And together, they manage to teach the Emperor empathy.
In one novel of The Highlands Of Afon Theodore, a cat-like alien known as a Taik from the titular Highlands, falls in love with a human named Anna while at college on a multi-species planet. They can't have kids, but his culture is polygynous and she's okay with him taking other wives he can reproduce with, so long as she is First Mother. Unfortunately her father turns out to be a bit of a bigot, and affiliated with an organized crime syndicate.
Sandpaper Kiss focuses on cat-girl Lucy, but it isn't until the end of the book that narrator Mark admits to romantic feelings for her. Word of god says this was originally intended as a Mayfly–December Romance, but the bulk of their relationship was kept in the background for a possible sequel.
The kandra are an amorphous species of shapeshifting spies and infiltrators whose jobs sometimes require intimacy. This becomes a plot point in Shadows Of Self, when it's revealed that Lessie was a kandra, who spent more than a decade married to Waxillium, acting as his bodyguard on Harmony's orders. Under happier circumstances, Wayne gets along quite well with the boistrous Ladette kandra MeLaan; they spend some free time smooching in Bands Of Mourning.
Humans and koloss are also apparently able to interbreed, although the koloss mentioned in the later books appear to be significantly more sane and civilized compared with the berserk monsters in the first trilogy.
Kris, a Terran, and Zainal, a Catteni, in the Catteni. It's a plot point that Catteni are biologically very similar to Terrans.
In Homecoming by Anne B Walsh The Lyrror and Mazor can transform themselves into human shape and interbreed with humans. This transformation costs them; Lyrror tend to suffer swelling of the joints, while the Mazor cannot walk without pain. Offspring can freely switch between the forms of the two parents, though their non-dominant form will still suffer the same ailments.
Spinnock Durav, a millenia old Tiste Andii from Malazan Book of the Fallen falls in love with the teen-aged human priestess Salind. He is appropriately creeped out by this.
Myth Adventures: Tananda the Trollop is open to dating practically anyone male, provided they're attractive by their own species' standards, rather than limiting herself to Trolls (her kind's male counterparts). Aahz is implied to have fooled around with all sorts of ladies from dimensions other than Perv, up to and including Sibone, a serpent-bodied Caffiend. Skeeve's first genuine date was with Cassandra, a vampire. This trope may also be applicable to the Happily Married Massha and Hugh Badaxe, assuming Jahks and Klahds are considered to be separate Human Alien species.
In Alice, Girl from the Future the humanoid alien Iria Guy marries human Tadeusz Sokol, and they have a daughter. However, it's a mild case since the only (visible) major difference between Iria's species and humans seems to be that she has purple eyes.
There is the unclear case of Rat's parentage, since he's an arthropod, and also a shapeshifter, and here the author got really confused in continuity. But Rat also seems to have a humanoid mother, and he himself states he inherited the shapeshifting from his father. However, there's no definite proof that he was telling the truth or that the Pirate Queen is his real mother at all.