I think this is Mieville's first actual sci-fi book, and he does try to go for the alien thing. As well as weird aliens, the start of the book just starts using words without explanation, leaving you to back-fill the details as they appear, and the human characters aren't full of twentieth century standard Western norms, either. The drop-you-in-it approach was good, the humans a little naff. Space travel is glued on the side in a way that doesn't really do much for the main plot.
So, the main plot. Basically it runs along the lines of, blah, background, oh no, sudden crisis!, resolution. Just as you get used to the world as it was set up, it's turned upside-down. The eventual resolution is handled pretty well, but the crisis that forms the middle of the book runs on far too long. Perhaps it's deliberate, but I found it dull.
And what is the nature of this crisis? It's about the aliens and... semiotics! Yes, the first semiotics-based novel I've read. Ok, it doesn't actually use the words 'signifier' or 'signified', but it's near enough. Sadly this bit doesn't seem plausible to me, even if the story is taken as a metaphor. It's a nice try, though.
Overall, The City and The City is punchier and more interesting. This is by no means a bad book, but I think it could have done from being condensed a little.