Wow, this all sounds delicious! There are a lot more paleo-friendly dishes on this menu than any of my local Mexican places. Any of the ceviches would be good. I wonder what "skillet style" means. You could get any of the tacos and just eat the fillings. If you do dairy, you could get almost anything and then get a side salad instead of the rice or beans. If not, they could probably do it without the cheese if you ask.