Ok, so I start to download a map. The server changes maps, a second map appears in the box. Then the first map d/l finishes, and the map comes up (while the second one is downloading still), and I see a black screen with random models floating around. I do a vid_restart and everything's ok.

Yes, I've noticed that this happens if a second map is started before you've finished loading the first. An in-progress bug I guess

This can't really be, but I'll investigate this later. The map download code should already explicitly catch this, but maybe some later change broke it.