I totally agree. I don't think Lions or Priviledge are romance. But they both have strong elements of romance. (Almost every fantasy novels have some elements of romance, hence my formulation ^^)
I don't think Priviledge of Sword revolves any more around the romance points than Lions do. Swordspoint may set romance as more central, but even there, I wouldn't call it a romance novel. There are other driving points, the picture of a social milieu (comedy of manner), the various intrigues, all of Michael's subplot, the elements of swashbuckling, etc.
Theme is not the same thing as plot, nor as tone. I think you can address a lot of different themes through a lot of different genres, so I'm not sure how relevant it is.
That didn't disturb me. Also, I wouldn't have called it "nationalist" (it's a bit avant la lettre for that). But attachment to cultural identities (with religion playing a big role to those cultures) is a natural thing to treat given the subject. I didn't feel like Kay was trying to make a point about how attached we had to be to nationalist ideas so much as aknowledge the strong role that those cultural identities play in people's life, in their histories (with smallcap and bigcap H), in their motivation, and in their art...
Of course I have personnal ties to all three identities (Jewish, Arab, and Western), so that whole theme had a lot of resonnance to me.
I liked it, but I would have liked it so much more if I had been feeling Kay was playing with me.
I didn't like the epilogue much either, so i guess I'm with you on your spoiler point too, although maybe I wouldn't go as far as you