There could be advanced implementations (like with the remembered passwords, where YT would store a list of seeded hashes of your viewed videos). But they are that: advanced implementations, that impose an extra cost.
Though I still think "not remembering watch history" (and adjusting what you are shown based on that) to mean that a functionality that doesn't have anything to do with tracking (because it only requires information from your current session) to be a little lazy.
You wouldn't expect a slide-show of images to be shown in random order, just because you didn't consent to the cookie banner.
But in all fairness - I really like youtube's auto-play and suggestion algorithm when it comes to music. I use it for free and I haven't seen an ad in years so I don't want to complain :)
I even went so far to seek out a website that does it for me, and which I set up as a bookmark https://youtube-playlist-randomizer.bitbucket.io/
Altough, seems like the site is now broken
Actually not sure if it's even that far fetched. Making the logged-out-experience worse on purpose is something all the big internet firms do.