I had this same experience when I moved from metropolitan Texas to a high altitude location in the mountains of Colorado. I would take my dog for a walk at 2am and just get stuck staring upward.

The first couple of nights, I was amazed at what I could see, but then I was a bit annoyed about this one strip of clouds that was blocking part of my view across the entire sky. The next night I realized it wasn't a cloud :). "My God, it's full of stars."

Portugal is relatively close to NL, and it has some spectacular sky viewing which isn't too remote from villages or places to stay.