Walleye in all its varieties of preparation is big in Minnesota. Any bar/grill/restaurant worth its salt is going to serve a fried walleye sandwich if it is offering sandwiches on its menu.
Genuine wild rice soup is another strong regional dish in Minnesota.
The breaded pork tenderloin sandwich is distinctly a heartland favorite centered through the I state axis of Indiana, Illinois and Iowa and states bordering on those three to a lesser extent.
JeffG, Would that catfish restaurant have been in Colfax, IN? That is the one I remember driving to for miles and standing in line.