Maryland and Virginia are really the only states on this list that are different simply because of borders.
-N.Mex. and Okla. are only slightly bordered
-Ill./Ind. is explained mostly (but not only) by Chicago
-Eastern Wash. is quite similar to Northern Idaho
-Inland Calif. is relatively conservative (and Ariz. is pretty moderate anyway)
-The other three pairings (Mass./N.H., N.Dak./Minn, Iowa/Neb.) have very different population densities (and western Iowa is also very conservative)
But MD and VA have comparable densities and race distributions, but are very different culturally and politically.
Good point. I was looking more at the totality of each state, not taking into consideration if the parts of the states actually near the border are similar to each other or not. If the question was "What state border causes the greatest political change when crossing it?" then MD/VA would win hands down. Of course, you are free to apply whatever criteria you'd like yourself.
If DC counted as a state, than the District of Columbia and Virginia, of course, would win this poll easily.