oaxaca and chiapas are great. some places in oaxaca get to be unbearably hot. and i dont mean, too hot for a gringo, i mean, too hot to even exist. so check that out beforehand. craziest thing is that some places are extremely warmer than others no matter the small distance between them.
If you are unsure about where to land first, go to san cristobal de las casas in chiapas. thats a beautiful and relatively safe place to be before you get used to be in mexico (if that stresses you). Also, theres a huge amount of travellers and a well developed alternative scene made both by chiapanecos, mexicans, latinamericans, europeans and northamericans. so you'll be connected and informed in a heartbeat there and you will be able to decide better after that. beware that its very easy to stay there for years (which is allright)