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. The Blackthorn family is said to have some fey blood 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, 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 Silver Metal Lover, by Tanith Lee, and its sequel, Metallic Love, in which, you guessed it, girl falls in love with robot.
Fritz Leiber's novel Wanderer included romance with an off-world female from a feline race. Think serious scratches down the back. Leiber's 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.
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 Angua also had a relationship with an ordinary wolf, implied to be the descendant of a yennork (a werewolf stuck permanently on 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 and Lady Margolotta.
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 laughs and occurring off-screen in the past, was the romance between Corran Horn (Human) and a ferret-like Selonian. 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. Corran also brings up the point that dating outside of your species can be problematic in other ways - what if your partner is used to giving and receiving love bites? With ten-centimeter teeth? Though thankfully there's no indication that he has personal experience in that particular area.
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.
Star Wars literature in general tends to have a fair amount of Interspecies Romance, and sometimes between rather disturbing couples. One example would be Dice Ibegon and Lak Sivrak, a female Florn Lamproid and a male Shistavanen. The latter looks like a Wolf Man... the former? A snake-like body, six clawed legs, a poisonous sting in the tail, and four long, curving fangs forming a ring around their circular mouth. And the two were explicitly stated to be physically compatible and very much attracted to each other...
And they appeared in the original version of A New Hope too.
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). 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.
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.
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.
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.
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.
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.
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.
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, 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...
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.
This is a recurring plot in the Psy/Changeling series by Nalini Singh. In the near future there are humans and two subspecies, the Psy and the Changelings. A lot of the romances take place between members of different subspecies, with all the cultural and psychological problems that entails.
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, lived with him half a year, but ended up melted by fire. 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.