I'll nominate Shards of Honor
by Lois McMaster Bujold.
Cordelia Naismith, Betan Survey Captain, was expecting the unexpected: hexapods, floating creatures, odd parasites... She was not, however, expecting to find hostile humans on an uninhabited planet. And she wasn't really expecting to fall in love with a 40-plus barbarian known to cosmopolitan galactics as the Butcher of Komarr. Will Mother ever understand? And can such an odd beast as love survive an interplanetary war?
This is not your typical romance. In fact, it has a lot going for those that aren't too fond of romance.