We just took some WI expats to Sweeney's Oakcrest Tavern (5371 Old Middleton Rd.) for perch and cod and they were very pleased. It's cozy, wood paneling, 5-6 beers on tap, great burgers too.
But there are lots of great choices in Madison - Madison Fish Fry is the best place to start a fish fry search: http://madisonfishfry.com/
5371 Old Middleton Rd, Madison, WI 53705
Have only had lunchtime burgers at Oakcrest, so I cannot say one way or another.
Madison Magazine just came out with its "Best of Madison"
#1 - Avenue Bar
#2 - The Old-Fashioned
#3 - Quivey's Grove
I have been a devotee of Avenue Bar for years...relatively convenient for me, and the food has always been solid. The independent owners recently sold to a local restaurant "conglomerate" called Food Fight. The ONLY time I've ever been disappointed was the last time we were there. The fish was greasy and the chowder still had flour lumps floating around. Everyplace has an off night, and we DID get there pretty early (the first pancake is never the best).
As to Old-Fashioned, I really think you would enjoy it. They have fantastic walleye and everything else is spot-on. Notice how many places it is mentioned in the writeup.
No personal experience at Quivey's.
6261 Nesbitt Rd, Fitchburg, WI 53719