I'm a native speaker of German and I do have some experiences with slavic languages. I live near the settlement area of the Sorbian minority.
Polish - fluent
Russian - basic
Czech - basic
Ukrainian - basic (started one month ago)
Sorbian: To me Upper Sorbian sounds like a Western Slavic language spoken by a native speaker of German with a very strong German accent. For some reason even the written language looks somehow awkward to me. Among all Western Slavic languages it is definitely the one I understand the worst.
Upper Sorbian on German TV
Czech/Ukrainian: Both languages are very closely related to Polish, but I didn't understand a lot before I started learning them. But when I did, it actually took me only a few weeks to achieve some kind of fluency in both, which you wouldn't expect so quickly, when you begin to learn a new language.
Slovak: It is closer related to Polish than Czech, but after taking classes in Czech, it is a little less intelligible to me compared to Czech. When I went to Bratislava a long time ago - I only spoke Polish at the time - the Slovak spoken in Bratislava sounded a little like Austrian German to me, but I didn't understand a lot to be honest.
Russian: Understanding spoken Russian has been always hard, even after taking classes. In some respects Russian is close to Polish, but in others it seems to be really remote.
Slovenian/BCSM: I do understand a few words i both written and spoken language. Only sometimes am I able to get what a longer conversation is about. On the other hand once I overheard a conversation between a Croat speaking slowly and clearly to a Pole about a recipe and I understood almost everything. I hear a little Italian accent in both Slovenian and BCSM.
BTW: In my humble opinion the most beautiful Slavic languages are Polish, Ukrainian and Slovenian.