I know finding an ESL job on ones own through the internet can be risky and time consuming. I went through this process several years ago and spent the two years after graduating teaching over there.
Where: Shandong山东, Zibo淄博 (http://en.wikipdia.org/wiki/Zibo)
I taught in Zibo for 2 years and then lived there for an additional year after that. It's a smaller tier 3 city that is surrounded by countryside and nearby mountains. What I liked the most was it was a biking city with designated lanes. I'm not much of a city person and found it much more peaceful than the time I spend in Beijing.
I was really pleased with the entire experience and if you're interested I can put you in direct contact with the person who helped me. Just shoot me an e-mail at josh@skritter.com if you're interested or have any questions.
*As a disclaimer I don't get anything out of this. It's purely me sharing the opportunity of a good and vouched experience.*