I've only eaten at the Airport Inn once since it was rebuilt and it was a horrible experience. It was cramped and crowded with lousy service and none of the old atmosphere. I'm not sure, but it seems like their pizzas changed after the fire, too. I think the original pizzas had more or better sauce. Most people don't like much sauce, but it makes or breaks the pizza for me.
As for Taco Johns, I'm sad to hear of it's demiss. I have many fond memories of hundreds of cheap meals there. I thought it had a better taste than most of the Bell fare. Plus, I could get custom built. A softshell with nacho cheese, sour cream and my own little secret ingredient (lemon juice) made a sloppy meal, but man was it addicting.
As to the original post, I fear that MC's glory days of having several good steak restaurants has suffered from fast food and lifestyle changes. Don't think there are enough middle class customers to keep them profitable. I will encourage you to make a special effort to try Miles City's unique food, called a "Paco", which is hopefully still available at the casino at the NW corner of Main and 9th? It's a deep-fat fried pocket bread stuffed with burger, onion cheese served with Jalopeno peppers whose juice should be squeezed over the exposed stuffing as you eat it down.