
I'd suggest Suzuka, but if you thought Naru of Love Hina was a bitch...
You might want to try Stellvia, it's a sci-fi tale of a bunch of Space Academy cadets in training to prevent a second catastrophic event from wiping out mankind (space opera!). Trust me, there's romance.
Ai Yori Aoshi has a bunch of fanservice-y content, but the core story about the relationship between Aoi and Kaoru is pretty sweet. They admit their feelings for each other pretty early on, though. But there's not much action....
There's also Ah! My Goddess/Oh My Goddess! and the AMG Movie.