Well, there appears to be one Landon 36-Eisenhower 56 county: Oglala Lakota County (formerly known as Shannon County), SD. Today it is 94% Native American and the poorest county per-capita. Seems a fascinating case, maybe it swung because more Native Americans were voting by 1956, rather than voters actually switching?
I'm inclined to believe that more Native Americans voted Democratic in 1956 than in 1936. With that said, that county in South Dakota is weird - see also the unexplained massive surge of voters it saw in 1940.
You might be right - the GOP Presidents of the 20s, particularly Coolidge, were pretty progressive for their time on Native American civil rights. Maybe that was still having an effect by 1936.