Now this is a weird problem: A machine with lightdm, set to auto-login a user, started the GNOME-session, but that was hanging (i.e. not even updating the background picture), and only continued after moving the mouse around for a few seconds.
Turns out that something in the session needs enough entropy to be available! (i.e. was reading from /dev/random or using getrandom(2))
I chose to go the easy way: apt install haveged (a daemon which provides additional entropy based on some CPU timing stuff)