Before I give you my West-Slavic perspective, let me give a remark that several dialect continuums exist within the Slavic language family, binding the languages together - albeit post-WWII migrations and mass media disrupted it to an extent. For example, as far as I am aware, a Polish Silesian dialect is very close to the Silesian dialect spoken in the Czech Republic. Polish dialects along the Carpathian mountain range are very close to the neighbouring Slovak dialects, and Polish dialects in Eastern Poland, along the Bug river, are very close to rural Ruthenian dialects of Westernmost Ukraine and Belarus. Consequently, official languages which are based on more central dialects, differ much more than their local counterparts.
Secondly, there is a small group of words, including the basic words for everyday things, body parts, personal pronouns, some terrain forms, foods, which are commonly used in all/many languages, even in distinct language groups. Dom, chleb, ryba, woda, rzeka, morze, góra, mama, mięso, ręka, noga, głowa, iść, jechać, jeść, biały, zielony, niebieski - are often almost identical or cognates (not always though). A specific example which came to my mind is a an inscription I found years ago painted on a barrow in Southern Bulgaria: "водата е мокра". In Polish we would say "woda jest mokra" (the water is wet), and apart for a definite article/suffix in Bulgarian, it sounds almost identical to Polish (albeit in general, Bulgarian is very distant and difficult to understand for us). Anyways, these Old Slavic traces make identifying later influences more difficult, at least for non-linguists.
Thirdly, sources of professional and "educated" vocabularies differ from language to language. In Polish educated vocabulary comes mostly from Latin (commonly taught in the Middle ages - of course considering, what 'commonly' meant at the time), French (a second and often preferred language of the educated classes until some 19th century) or German, in the Czech language - mostly from German, surprisingly I also recognised a significant group of German loanwords in Russian. And I'm not referring only to the modern-day artificially coined scientific terms based on Greek or Latin roots, which are pretty much unified globally. But for example many Polish words referring to an urban life and organisation (ratusz, burmistrz, rada) come from German (Rathaus, Burgmeister, Rat). The same goes for a number of artisan tools and techniques, etc.The reason is simple: for several hundred years in Middle ages a number of German or Germanic settlers migrated to Poland, and albeit in most rural areas they were fairly quickly diluted among local Slavic people, in towns they formed local majorities and retained their cultural distinction until some 19th century (in central Poland; there are regions where the German populations survived until WWII). Besides, the towns themselves were often settled based on the laws of Magdeburg.
A religion was mentioned: indeed, Old Church Slavonic liturgy might have contributed to a conservation of certain old words and structures in East and South Slavic languages - hence perhaps a distance between Russian and South Slavic languages seems to be lower than between the West and South Slavic languages. But for example, BCS is officially pretty unified and mutually comprehensible, albeit Croats were historically Roman Catholics, Serbs - Christian Orthodox, and Bosnians were muslims.
An influence of Russian over Polish: indeed, it's not huge, despite Russian was a language of education in the central Poland for over a hundred years since early 19th century. But it left traces mainly in some constructs and fraseologisms rather than on vocabulary, so they are more difficult to trace for the native speakers. An asymetry in undersanding, referred to by
@rushalaim, depending on the age and origins of the Polish person, may come from Russian being taught at schools during communist times, or perhaps from Ruthenian influences along the Eastern border. Anyway, albeit I barely speak Russian, I retained quite a grasp of passive understanding of the language, which also helps me with Ukrainian.
This brings us to intelligibility of the languages, and the mileage vary. Everyday Slovak language is pretty much intelligible for an average Pole. When I return from more distant countries, language-wise, in Slovakia I feel almost at home already. I recall conversations with the Slovaks, where everyone of us spoke their mothertongue, and we were mostly fine with that. The Chech language is significantly less intelligible, and a conversation requires quite a lot of effort, but to an extent it's doable. I do not have much experience with Upper and Lower Sorbian, minority languages spoken in South-Eastern Germany. Kashubian - a minority language in North of Poland - is almost unintelligible for me, at least in its spoken form. In writing it's easier, and I understood 60-90% of the text depending on a particular fragment, albeit understanding the topic of the article was a great help. I understand quite a bit of Russian, but I would attribute it to an education in 70s and 80s, rather than to proximity of the languages; there are more similarities - or parallels - in patterns and structures than in vocabularry. The same goes for Ukrainian: I have an impression that my fading Russian contributes more to understanding the language than my native Polish, at least in case of the official language. However if I overhear immigrants, who probably come from the Western Ukraine, it may be both. With regards to the South Slavic languages, I agree with
@Eirwyn - to me they look like a bunch of recognisable morphemes randomly scattered around completely cryptic mass of text - with Bulgarian being more understandable than Croatian though - which again may be because of my Russian learning in the past.