Ahhhh, indeed! I changed the hostname in /etc/hostname a while ago, but I was not aware that I also need to apply this change to /etc/hosts. I have done this now, and the issue with Firefox and apt/aptitude starting slowly is now gone.

It's interesting that I have changed /etc/hostname without changing /etc/hosts in the past on (non-virtual) machines, but never observed this issue.

Anyway, THANK YOU VERY MUCH for steering me to the solution!