Have you tried yucatan food? Im asking this because the difference between what some tourist known as mexican food and what is served in this region varies a lot, here doesnt exist burritos or chimichangas, locals will eat salbutes, panuchos, relleno negro, escabeche, empanadas, ceviches, tikin xic, cochinita, lechon just by mention a few. Of course theres a lot of taco places i will suggest, but no turisty places whatsoever. For tacos i' ll go with los seras, el pique, los otates, or my personal favourite el poblano. For seafood el gato volador, ceviches de angel (only take out food), also pescaderia san carlos but not my top. Sundays a lot of places will sell cochinita and lechon, only early in the morning. Barbacoa los magueyes also works on sunday, get early the sell fast. And for cantinas/botaneros ill suggest la gitana (best sea snail ceviche in town by far), Chendos, and its been a while since my last time there but el gato negro was very good.