If you are driving I-10 through Deming, NM, do yourself a favor and stop at El Mirador. It is a small, pink, family-owned place at 510 East Pine - which is also known as the I-10 Business Loop. They are open Tuesday from 6 AM - 6:30 PM, Closed Sunday, and open other days from 6 AM to 9 PM.
Once you stop, do yourself another favor and order the huevos rancheros green...no matter what time you get there. If it is lunch or dinner time, you will get a basket of chips and bowl of salsa, as well as a sopapilla to finish off the meal. But the breakfast gives you plenty of food, and you really don't need the extras. Two eggs, your choice of style, on corn tortillas covered in a fabulous green sauce and with cheese on top. It is served with beans and sliced potatoes as well as a corn or flour tortilla on the side.
It is popular with locals - as well as the local law enforcement. You may have to wait for a table, but it's worth the wait.