If you go into Sedona check out Red Rock BBQ, was real good.

1/4lb pulled pork, 1/4lb pulled chicken, 1/2lb beer brisket and a rack of baby back ribs for $50 ( i think that was the price)

 

I take it your hotel will be close to south mountain. I would go check that out in the evening, it's a nice view of the whole city during sundown and the drive is nice as well. The only thing is that it gets boring pretty quick so just have something planned ( like dinner or something)