I'd say the difference Russian vs. Ukrainian is very similar to Czech vs. Slovak. I, as a born Slovak, can understand virtually everything from Czech. Many books in Slovakia are not translated to Slovak, they are imported from the Czech Republic. Also Czech TV stations are widely spread here, TV dubbing is left in 99% Czech etc.
On the other hand, as the Czech Republic is much bigger market, they usually translate everything, dub everything into Czech and they, after the split of Czechoslovakia, lost contact to the Slovak language. So an average Prague citizen has big troubles to understand Slovak (specially youth, born after 1989).
But as mentioned, it all depends. If someone lives in his village whole life, does not read books, watch foreign movies, meet new people... even a dialect from his own country can be strange to him.