I’m Romanian myself, and the first time when I heard someone speak Albanian was as a teenager, when zapping through the satellite TV channels and landing on a Albanian news segment.
I was very intrigued because it felt that the lady presenting the news spoke a language that I should have understood, and yet I didn’t, not one word.
Later on I found out that there’s a name for that, i.e. for languages that have very similar intonation, but I forgot which one was exactly. Granted, that similarity between how Romanian and Albanian sound is most likely caused by our common Thracian/Dacian substrate.