Perdido Street Station by China Mieville

This book is the first of Mieville's Bas-Lag series and was just as weird as the third one.  His world is mostly steampunk with some magic/occult thrown in.  His writing is... different, but I haven't decided if that's a good thing or not.  The story was strange and overly convoluted, but the third book makes a bit more sense now because I know more about Bas-Lag.

He does introduce some interesting concepts like the punishment factories and Remade so I recommend you give this book a shot.