Gonna toss in my recommendation for the Rihannsu books by Diane Duane. No list of great Trek novels is complete without them.
You probably will want to read her other two books from the "old days", Spock's World and The Wounded Sky as well, as they have elements and characters that tie into the Rihannsu storyline.
Specifically,
The Wounded Sky introduces Duane's particular version of the
Enterprise and its crew and takes place about a month before
My Enemy, My Ally, while
Spock's World falls between
The Romulan Way and
Swordhunt. They tend to be overlooked because they're not specifically Rihannsu-related, but that's a mistake, because they're both integral to the overall Duane continuity and IMHO are better than any of the Rihannsu books.
There's also
Doctor's Orders, which only peripherally connects to the other Duane books, because it was written during the Richard Arnold era when continuity and recurring original ideas in the books were suppressed; but it does feature two of the human characters from Duane's other books, Lia Burke and Janice Kerasus, even if her alien
Enterprise-crew characters are missing.