Please do.
Okay, I'm pretty sure none of these are actually from the romance genre... but meh.
Rainbow - One of the main characters die, and he is in a relationship, bit their relationship was never in the spot light. The death has a greater impact on the people around him than on her (it focuses on how it affects the friends more at least).
Phantom: Requiem for the Phantom - The romance can be rather stale at times (it's a romance between people who can barley feel emotions, what can you expect), and really does take a step back for all the action and edgy shit going on. But this one should hit you right in the feels.
Millennium Actress - An old women tells her life story on how she worked her way up through show business and her encounters with a mysterious man, and how she cased him for most of her life. This one has a real nice bitter-sweet vibe. Highly recommend this movie.
Gankutsuo - This is where I start scrapping the bottom of the barrel. Really it's just about revenge, but I think the Counts love plays a role. There is also romance between other characters, but Albert's a faggot.
Gungrave - this one is primarily about the rivalry. But it has pretty important romantic themes in the first half of the series, and they bleed over into the second half and are the reason our main dude acts the way he does a lot of the time. This is a heavy action show. But I found the first half to be brilliant.
The Garden of Sinners Movie 5 - You're gonna have to watch 4 movies to get to it lol, but you should watch these anyway. One of the best series I've seen. Okay, this is more of a one sided love between a main character of the movie and our lovely heroine, but it's played to great effect. Watch it, watch all of kara no kyoukai!
From the New World - No, I'm not just tricking you into picking the show back up again. But in the second arc we have a massive love pentagon (#freelovebaby), and shit starts to get real. The moment one of our main kiddies dies is absolutely heart breaking, but it also has massive influence over the third arc and finding out just what the fuck is going on in this perfect little world.
So yeah, none of them are actual romances. But they are all shows I would normally recommend, but they might not be what you're looking for...
Hope they help though.
Edit: oh and School Days... Can't forget that beautiful boat 0_0
I haven't watched Fate/Stay Night yet, should I wait for the re-release?
In all honesty, I'm not sure. If the remake was just around the corner, I'd say wait. But I have no idea when in 2014 it'll air... I can tell you I found it unbelievably hard to get through after watching fate/zero. I found the pacing to be terrible, the characters were inconsistent, poorly developed, and just made stupid decisions considering they signed up for a death game... The animation isn't anything amazing by today's standards, and there was so much I just didn't like about the show.
Personally I'd wait, but if you think it is something you'll like you might as well. It just means you'll have to watch the same story twice in a year (who knows, if they do the Heaven's Feel arc, it should be pretty different). I might be able to recommend Fate/stay night: Unlimited Blade works, but the movie assumes you've seen the series and cuts through the first five eps in a strange montage...