The City and the City
I read this a few months ago and absolutely loved it. The writing style and setting reminded me of Le Carre, Graham Greene, and Ursula Le Guin (all writers with a particularly clear and attractive writing style, of whom I am particularly fond).
It's a spy novel cum whodunnit set in what seems at first like a fictional Central European city inspired by Cold War Berlin, but soon proves to be something even odder and more mysterious: two cities with different cultures existing in almost the same space, and separated by the intervention of some mysterious force.
Philmophlegm read it on my recommendation and didn't like it particularly: I think mostly because he was focussing more on the plot and less on the setting than I was. A number of people complain loudly on Amazon about the grammar. My take on that was that Mieville is doing what Le Carre does, and writing in a particular 'accent' to convey the voice of the character. The character is not writing (or thinking) in English, but in another language, and this affects how he structures his thoughts. This is a device widely used by Le Carre and is one of the many things I like about his writing - but he doesn't generally do it extensively with viewpoint characters, so it's clearer what is going on.
Perdido Street Station
OK, now here is a fat book. A really fat book. One could say that it's a bit wobbly.. And again, it's a book that contains strong echoes of other writers - this time Mervyn Peake and M John Harrison. Harrison, if you remember, is the author of another Fat Book - Viriconium, which is the book that wowed me spectacularly, then disintegrated into interpretive dance and people randomly turning into locusts.
You can definitely see the influence of the locusts: insects play a major role in Perdido Street Station, and there is a race of people who have 'headscarabs' - their heads are insectile in shape.
The book is also quite Gormenghastly. I love Gormenghast, but one of the joys of it as a book is that it's not actually that fat; it's a relatively spare, lean book where every line makes an impact. This isn't like that. Nothing happens quickly : everything is described in loving detail, from the many peoples of New Crobuzon (as well as the insect-people, only the females of which are sentient, there are cactus-people, bird-people, frog-people, idiot demon-people, humans, surgically transformed people with robot or animal aspects, and intelligent hands that control host bodies) to the sewers, the university, the administrative system...
For me this was just too much. I felt there was a good book hiding in there somewhere - possibly even several good books. But he's tried to do too much at once and ended up with a distinct feeling of 'are we nearly there yet?'