The map on that page shows post-2000s redistricting geography (at the earliest, the 2005-2006 term, as Maine shows the districts drawn in 2003 for the 2004 elections) even though the the districts at the time (1991) were based on the 1980 census. The map just shows the representative for district #
x in what was after in 2005 or so the district #
x, which could be totally different. That's why several districts in states which have gaines seats since then show "Unknown Representative." And several other Congressmen from states which have since lost seats aren't shown (Nick Rahall in what was then WV-4 to name one).
The Republican in Vermont
That's Independent Bernie Sanders. Definitely not a Republican, although Vermont is shown in the Republican color (the "No" vote pattern) on that map. Although that was his first term and Republicans held the seat for several terms right before that.
The most awesome: Indiana. The democratc control all the rural districts whereas the republicans control the district of Indianapolis.
Indianapolis was in IN-10 back then, which isn't shown as Indiana didn't have 10 districts in 2005. IN-10 was represented by a Democrat, although in its 1990s incarnation the Indianapolis seat (still IN-10; it bacame IN-7 after the 2001 redistricting) was kind of a sleeper seat that Democrats couldn't take for granted, although they never actually lost it (they did in 1972 but the defeated Democratic incumbent won it back two years later).
Basically, that map is FUBAR, but your points about Idaho and Utah stand, and the south to some extent although some of the rural-looking districts on the map could actually have been black majority districts in reality, I'm not sure.