Pokémon has a LOT of examples. Actually most romance involving a Pokémon is, except when it's between a gender counterpart race such as Nidorina/Nidorino and Volbeat/Illumise or in some cases, two Pokémon of the same species. Several Pokémon, such as Meowth, Ash's Chikorita and Aipom and Harley's Cacturne have shown interest towards a human, but a human having interest for a Pokémon has yet to come.
Most famous is between Ash and Latias, a Legendary Pokemon to boot, from Pokémon Heroes.
Dawn's Buneary had a crush on Ash's Pikachu for a long time.
A Phione became attracted to Buneary, and angrily tried to fight Pikachu over her.
Humorously, Phione are genderless and don't reproduce that way.
In one episode, Jesse's Wobbuffett fell madly in love with a wild Kirlia, so much that it was willing to disobey Jesse in order to protect it. It wasn't exactly clear how the Kirlia felt about it. (This makes a little sense, seeing as Wobbuffett and Kirlia are both Psychic Pokemon, and thus at least have something in common.)
Special mention goes to Ash's Oshawott, who falls for practically every (assumed) female Pokémon he meets.
In all fairness, at least in the cases of Pokemon who have crushes on Pokemon who are not their species, two Pokemon do not have to be the exact same species to be biologically compatable with each other if the video game is any indication. (In the game, you can breed a male with a female if they share an "Egg Group", and several different species belong to each Egg Group.)
Though their have been instances of the subject Pokemon not being in matching egg groups.
Goku & Chi-Chi and Vegeta & Bulma are both Saiyan/Human pairings.
Later, there's Gohan & Videl (Half-Saiyan/Human).
Since there are no female Saiyans left, all of the remaining Saiyans' romances, as well as their offsprings' romances, would represent this trope.
Also Krillin and Android 18 (Human/Cyborg).
In the OVA Dragon Ball: Yo! Son Goku and His Friends Return!!, Vegeta's long-lost brother, Tarble, comes to Earth from a distant planet with his wife to warn him of a (not-so) dangerous new threat. Of course, you wouldn't guess that he was married to Gure by looking at them, since he's a Saiyan and she's a distinctively non-human (or Saiyan) -looking alien who barely comes up to his waist.
And then we discover that Belldandy's appearance (along with all the demons/gods in the series) is not her real appearance, it's just what we see. If a human sees a god/demon true appearence, that human's mind can shatter.
The manga Nekoyome (literally "Cat-Wife") is about the married life of a human male and a female nekomata (who is a cat-sized bipedal anthromorphic talking cat!)
Played with in Inukami!: During a Love Potion incident, Keita thinks about getting some interspecies loving with Youko and/or five of the other girls, until he realizes his kids would be half-dog, and is promptly disturbed about the whole thing. Kinda odd though since he knew at the time that Youko is a kitsune/fox.
Only in the Anime; the end of the Manga definately implies that a wedding is in the future for Keita and Youko.
Nozomi (human) and Kouji/Coco (funny plush-looking tanuki-thing from another dimension), as well as Komachi (human) and Natsu/Nuts (funny plush-looking squirrel-thing from the same other dimension) in (you guessed it) Yes! Precure 5. To make things worse, Nozomi is a middle schooler and Coco's human form is a middle school teacher.
Yes! Pretty Cure 5loves this trope. There's also all the subtext between Karen (human) and Milk (funny plush-looking rabbit-thing from that same other dimension). They are both female. Which leaves Rin as the only Cure not paired up with one of the mascots... and one episode centered around her and a ghost (not exactly different species, but close enough).
And then there's the recently revealed Magical Land, which seems to be mostly populated with Humans, Petting Zoo People, some Funny Animals, even the odd demon. All of this little world is implied to happily mingle and reproduce without much regard for species.
Kir from King of Bandit Jing hits on everything with two X chromosomes to rub together, and though he always gets rebuffed, it seems to have more to do with his personality than the fact that he is a bird.
Yu Yu Hakusho and its human/demon romances, namely Sensui and Itsuki (human and demon/yaminade), Yusuke's ancestor Raizen and a female doctor (demon and human), and also Kuwabara and Yukina in the manga. Hell, you could count Yusuke and Keiko, as well, because of his demonic atavism.
Sailor Moon SuperS had ChibiUsa fall in love with a winged unicorn named Pegasus. Partially subverted in that he was really after her mind, not body, as the theme of that story arc was basically pure dreams, which ChibiUsa would have as a child. Though many people were disturbed not by the implied bestiality issues (his true form was human after all) as much as the fact that ChibiUsa was physically only about 8-10 years old at the time, while Pegasus'/Helios' age is never disclosed in the anime (some dubs actually gave him a voice of a grown-up man). This is somewhat less of an issue in the manga: Word Of God stated that Helios is supposed to look like a seventh-grader (around 13-14 years old), and ChibiUsa herself eventually achieves a more grown-up form of Princess Lady Serenity (if temporarily). Additionally, in the manga she is Really About Nine Hundred And Two Years Old by the time she meets Pegasus.
There's also whatever the heck Peruru is in the SuperS movie and Chibiusa again. At the end she kisses him too. Pegasus has some competition.
Sailor Moon also had one of these in the side story The Lover of Princess Kaguya (basis for Sailor Moon SNon-Serial Movie), where Luna falls in love with a human astronaut Kakeru. This one is also partially subverted: not only Luna's crush on Kakeru is one-sided (he is in love with his co-worker Himeko), but Luna later temporarily achieves human form, and in the manga she is later said to be an alien, so this form might have been natural for her.
There's also an implication of Artemis having a crush on Minako. At one point in the manga he is actually peeping on her while she's in the bathroom (which ends badly for him after Diana innocently reports the incident to Luna). In the anime, Artemis gives Minako a bouquet of roses in one episode to cheer her up. Again, in the manga he is an alien with a human form, but this isn't revealed until later on — in fact, the cats being aliens from Mau was pretty much a Doing in the Wizard moment as they were never hinted to be anything more than magical cats (in the Sailor V manga Artemis is mostly treated as a housecat who just happens to be able to talk).
One chapter of Sailor V also had Artemis crushing on a small dog who happened to be named Luna-chan. While he probably mistook her for that Luna at first (the dog actually looks a lot like a cat, only giving herself away by barking), he still considers "marrying" her after the reveal until the dog turns out to be a disguised villain. A male villain.
In the Super S anime Artemis is implied again to feel like this... and mixing it with Hot for Preacher: his "target" is a beautiful Catholic nun named Sister Maria. Luna herself teases him a LOT for it, and thinks it's kinda cute. That's regarded moot soon, though, since Sister Maria becomes the victim of the week due to Tiger Eye kidnapping and mind-raping her, so the Senshi have to save her. It turns out that Artemis was just daydreaming about how he wanted cats to get married in a church, anyway.
Hippo and Yuuri in Mermaid Melody Pichi Pichi Pitch covers all the bases. Hippocampus that turns into a penguin that turns into a human falls in love with a tropical fish that also turns into a human. Whew!
Lawrence and Holo in Spice and Wolf: a human and a trickster giant wolf who takes the form of a young girl (+ tails/ears) for almost all of the time. In volume 3 of the light novels/the first arc of the second season, after suffering a great psychological blow, she offers herself to Lawrence, thinking a child they could have together would keep her from being so lonely. Lawrence gets to thinking about this as well, and asks Deanna whether there is any record of human-deity couples. Apparently, there have been many.
Both examples are more in the Ship Tease category than actual romances, but the two biggest cases in the Slayers series are Princess Amelia and Zelgadis (a regular human and a chimera) and Xellos and Filia (a demonic priest and a golden dragon). Zelgadis and Amelia's case is subverted in that the former was once a human himself.
In the fifth season of the anime, there is the mechanical doll Ozel having feelings for the human priest Rezo, which in this case is unrequited.
And in the fifth Light Novel, the silver tiger beast/cult member Duclis spoke to the human protagonist Lina during his death that he had grown fond of her.
The eponymous character of InuYasha is the product of a youkai (demon) and a human. He later goes on to have a romantic relationship with two human girls. Given the number of half-demons he runs into during the series (and a very enamoured wolf-demon), it seems that humans are a common youkai fetish, and vice-versa.
In one episode of the anime, a human woman named Princess Sara falls in love with Sesshomaru, Inuyasha's youkai half-brother.
It ain't a canon example by any means, but would that all interspecies romances looked like this◊ (One's a cyborg, one's a vampire. Different species!).
It's mostly Human Aliens, and then there's the question of how you count Tenchi (he's part alien himself), but it's a central theme of the Unwanted Harem the poor kid has. Even the battleships have the hots for him. Well, two of the most powerful battleships in the galaxy, anyway. One manga shows a Terran girl making her case by being the only HUMAN interested in Tenchi.
Happens all over Hyper Police: Natsuki is the product of this (Human/Goddess), Sakura (kitsune) has children with the timelost (human) samurai. Batanen (werewolf) has a huge crush on Natsuki (Half-humanCat Girl), and Tommy (werewolf) has 19 (!) children with Poe (Human) in the manga.
Gash Bell features Wonrei and Lien, the only human-mamodo team in the series whose relationship very explicitly goes beyond friendship. Fortunately, since Wonrei is one of the few mamodo who actually looks like an adult human (and one of the most human-looking mamodo of the entire series), the trope's usual creepiness is wisely averted.
Now that she is human, Yuichiro feels uncomfortable with the same kind of physical contact compared to when she was a dog, leaving Elga feeling heartbroken and unloved. Rino blasts him for not being willing to return Elga's (platonic but unconditional) love for him, after which Yuichiro realizes she is "still Elga" and gives her the pats, hugs and cuddles she's been missing. Once she understands the whole story, Emina is almost entirely accepting of the situation. The whole thing avoids, inverts or averts a whole bunch of expected tropes, including this one.
In One Stormy Night, Mei the goat and Gabu the wolf are "friends", with a relationship dynamic much more like male lovers, albeit subvertedly Star-Crossed Lovers, even opting, after the hardline disapproval of both their kin, to escape together to a distant place to be with one another forever. Gabu's carnal predatory instincts only add to this, seeming more like intense homoerotic attraction. In a later scene in the film, Mei agrees to be eaten if the one who eats him is Gabu, which gives Gabu an emotional breakdown, and they do not follow through. See also If It's You, It's Okay.
And for a more official example, we have Genya and Quint Nakajima, an Earthling and Mid-childan. Though since Quint was barren after sustaining near fatal injuries during a mission, she couldn't bear children. They found other ways to solve that problem.
This happens a lot in Blue Drop, what with all the couplings between human women and Arume. Somehow it results in Half Human Hybrids, despite both parents being female and both parents being of different species.
Eureka Seven: Eureka and Sakuya are Coralians that were created to test whether it is worthy for Coralians to coexist with humans and they fall in love with humans. The series takes this interspecies love approach seriously as Eureka constantly condemns herself for not being human and fearful of her lover Renton leaving her because of this issue, especially since their race are at war with each other.
Kyo Kara Maoh has Demon/Human relations. Although, for most of the series it is heavily frowned upon, to the point where Half-Demon Half-Human families have to live in their own villages.
Half demon half human offspring may or may not have magical abilities, as see by Conrart and Yozak (who have none), and El (who is ungodly powerful as a baby).
Bizenghast looks headed this way with Dinah (human) and Edrear (humanoid...bug...construct...thing). Edaniel also claims to have dated a human agent.
Yu-Gi-Oh! GX has Juudai x Yubel. Juudai swore his love to her after she was transformed from a human into a humanoid dragon, and that didn't change even after death and rebirth. He just forgot about it for a while. He got better. And so did she. There's also Taniya x Misawa, even though Taniya is fairly human looking. She can just turn into a tiger and has very pointed ears. (It has been suggested that the tiger is, indeed, her true form, but this has not been confirmed.)
GX is the series with most human x duel spirit ship tease, other examples are Sho x Dark Magician Girl (which is canon, even if they're not specifically together. Interest was shown on both sides.) and Fujiwara x Honest.
Given that Ahiru from Princess Tutu is a duck given human form, any relationship with her invariably involves some element of this, especially given the ending — Looks like Fakir isn't going to let the fact that they can't consummate get in the way of being together.
One Piece has human and mermaid couples, and even a fishman and giant hybrid.
To Love-Ru has a romance between a human (Rito) and at least two alien girls, Lala and Run.
In Ghost Sweeper Mikami Yokoshima goes after anything with a good looking female form. ghosts, robots, demons, dragon gods, wolves, foxes, etc.
Dragon Half is about a half-dragon Mink in love with Dick Saucer, a popular dragon slayer. Princess Vina is Mink's main love rival and a slime-half.
Otome Youkai Zakuro deals with the relationships between a trio of human males and half-Kitsune females in an interspecies military unit in Meiji-era Japan.
Technically, Neon Genesis Evangelion might count. Rei and Shinji because Rei is a (vat-grown) human-Angel hybrid. The Squee ending of Rebuild 2.0 only reinforces this: Rei previously states that she feels "warm and good" around him (though it's unknown if it's genuine attraction or motherly instinct; she is the clone of his mother, after all), then in the end he triggers Third Impact to save her from Zeruel. Shippers, rejoice. Also, if he meant what he said, Kaworu is a full-blood Angel who has the hots for Shinji.
Himawari gives us Yusura and her boyfriend Yonezawa, a kappa. Thankfully, he is the cute, friendly, anime-version of a Kappa, not an organ-sucking river monster. And they both love cucumbers...
There's two cases of this in Animal Yokocho. Issa the panda sometimes wants to be the main character Ami's boyfriend, and Kenta the bear and Ami's friend Ku are openly in a relationship. Sure, Issa and Kenta are technically stuffed, but they're obviously sentient...
Celty and Shinra from Durarara!!, the former being a Dullahan (a headless Irish death fae) and the latter being a somewhat eccentric human scientist.
In The Cat Returns, a girl called Haru, who has a long-suppressed ability to talk to cats, saves a darkly colored, odd-eyed cat from being hit by a truck on a busy road. The cat turns out to be Lune, Prince of the Cat Kingdom. In return, the cats shower her with gifts of catnip and mice. She is then offered the Prince's hand in marriage. Her mixed reply is taken as a yes, much to Haru's dismay. She later develops a crush on the Baron, a living cat figurine who promised to help her get out of the arranged marriage.
In Wicked City the human Renzaburou and the demon Maki eventually develop feelings for each other and consummate their love near the end of the movie. The person they were ostensibly protecting was actually steering them towards this outcome all along because their Half-Human Hybrid child — the very first one in existence — is needed for the peace treaty as living proof that humans and demons can co-exist peacefully.
Subverted in Eve No Jikan with the couple Koji and Rina; each believes the other to be human, but they are both revealed to be androids.
Later played straight with Sammy, who is heavily implied to be in love with her human master Rikuo.
Keroro Gunsou, aka Sgt Frog has many interspecies interest though it is one sided or unrealized love. The most prominent crush in the series is "Giroro" the reddish alien frog (called Keronians) to the human (referred as pekoponians) "Natsumi". the keronian, hard-boiled, combat specialist Corporal Giroro who wants to invade Pekopon (Earth) is deeply in love with the tomboyish Pekoponian school girl Natsumi (everyone knows this, except Natsumi....) who is considered an obstacle for the invasion. “She's the girl of their nightmares…& the girl of his (Giroro's) dreams.” There is also Angol Moa/Mois, a ditzy humanoid alien girl from the Angol tribe who has a deep crush on Keroro (an alien keronian from the 58th Planet of the Gamma Nebula). “I've kissed enough princes to deserve my frog…” Sergeant Major Kululu has this thing of watching Aki (the hot mom of Natsumi & Fuyuki) shower & seems to have a creepy thing for her, though she does not seem to mind him & thinks he is a cool addition.
Petshop Of Horrors: If you've had sex, it was with an animal demon in temporary human form.
The Mazinger trilogy (Mazinger Z, Great Mazinger and UFO Robo Grendizer) has several examples from romances between humans and humanoid aliens: Duke and Hikaru, and Kouji and Maria. And the you have Duke and Rubina. Both of them are aliens but they are from different species -and born in different planets-.
Sekirei is built on this trope, with the titular aliens falling in love with human partners. It's later revealed an Ashikabi is a Half-Human Hybrid, and their ancestors were Sekirei that married humans in ancient times.
In Wolf Children Ame And Yuki, this is a main plot point. Hana falls in love with a unnamedwolf-man, and the two have two children, Yuki and Ame, who both posses the ability to transform into wolves. This is then deconstructed slighty when the wolf-man dies whilst out hunting. The difficulty of having to raise two wolf-children alone on very little money, whilst having to keep their secret, and combined with being an first-time mother (and so unable to properly ask anyone else for help) ends up causing Hana and the children to move to the countryside in order to preserve their anonymity.