TOD:
There was an "authentic" Mexican restaurant back in NY that was pretty good (no, not Tacky Bell). When I moved out to Tucson, that's where I experienced really spicy food, at least chile pepper-wise.
There are several very good Mexican restaurants here. My friends who are Navajo, Mohave and some portions of their family intermarried with Mexicans, always use cilantro. I haven't seen anyone out here who isn't of Mexican background (and some Mexican Mexicans) not use cilantro. In fact, the local groceries that carry Mexican specialities sell lots of it. As a NY gringo, I never used it before I came to Arizona. Cumin may be an American afterthought as it makes food smell and taste like Doritos, which is a very Mexican(!) food.