The major caveat to this is that a great many science fiction books are not fictions of science, so much as they are fictions of technology, and not all technology is science. This is a very minor irritation professionally, but thus far I have been thinking of it as infiltration in terms of SF.
Now the challenge with "This book is science fiction if X is considered a science." is, of course, all the borderline cases. (Those are what make any act of categorization interesting.) Is economics a science? Is computer science a science? The further from general certainty a would-be science is, the more uncertain people are (in my very casual observation) to categorize the work as science fiction. The problem of subsuming technology under "science" for this purpose can complicate: if technology fiction is science fiction, then steampunk, clockpunk, and their ilk is all science fiction. (Note that this method says nothing about whether or not a book is also, or is instead, a work of fantasy.)
In the case of The City and The City, it is science fiction, by this method, if sociology is a science.
Ursula Le Guin's Lavinia is science fiction, by this method, if history is a science. It is, among other things, a book about historiography. It is a book which compares forecasts and hindsight to experiential reality. It is a book which explores what historical evidence lodges in our collective record, and how that record is dependent upon the subjectivities of the authors who made those records. It is a book which reminds us of the frailty of any record, and the importance of what can be gained from examining evidence in wider contexts.
There are no end of other categorization methods for science fiction which will or will not include Lavinia in the genre; they're all useful tools. This particular one boils down to what our (my) assumptions, prejudices, and definitions are of entire swathes of other kinds of knowledge categorization. I would argue that history can be a science, depending on the methods being used, and that Le Guin has treated it as such in this book.
(This post is a response to Lavinia's ranking at #8 in the polls results of the best novels by women in the last 10 years over at Torque Control.)