Perdido Street Station is as good a place to start as any, it's the novel that made his name and where most people probably start with him. You could also start with The Scar, which is set in the same world and follows on from Perdido Street Station, but not in a way which would spoil it at all. They both have the same appeal I think, a rich fantasy world bubbling with strange ideas.
Since this discussion he's written The City & The City, Kraken, Embassytown, and Railsea. I haven't read the last, or much about it tbh. Kraken is somewhat similar to the above two but without quite the same vigour. It's still good, but it's not his best work. Embassytown is a science fiction novel that depicts the interaction between human colonisers and their alien hosts, it is all about the unique language and system of thought of the aliens and the effects on it of contact with another civilisation/species. The City & The City is Mieville's least fantastic work, a detective story in a city divided between two nations with a touch of what you could call urban fantasty city planning.
They move away from the slightly steampunkish 'new weird' aesthetic that has been Mieville's milieu and as such are maybe not such good entry points, except that they probably point to the direction he is going in in future rather than where he's already been. Beyond that they are simply two outstanding novels, imo.
So I would recommend Perdido Street Station, The Scar, The City & the City, or Embassytown as good places to start with Mieville, depending on which you most like the sound of.