Thanks so much Conrad these are really great questions.
To your question of: "But am I wrong in thinking that supervenience only seems plausible because we're used to the simple logic and precise determinism of classical physics?"
So suprevenience turns out to be a surprisingly flexible way of talking about systems and scales. It doesn't actually imply that the microscale must be simple or deterministic. Noisy systems, or those with complex interactions or functions. Here I use it solely over discrete finite systems. For any such system there's some definable set of supervening scales {S}, which may be extremely large.
I'll note first of all that for most of what we consider physical systems this holds: for example, given a group of cells, those cells will have some supervening scales the definition of which seems, at least to me, pretty non-controversial. Same with say, the logic gates of a computer all the way up the supervening program of a web browser. In theory there is some mapping between the web browser and the underlying circuits, even if that mapping is *enormously* complex and unwieldy.
To your point that: "the speculative quest for a deeper-level physics hardly gives a picture of 'lower-level properties from which all the higher-level properties necessarily follow.' On the contrary, most features of the Standard Model are currently explained by random "symmetry-breaking.""
Perhaps the word necessary is confusing here. By that I mean, given the state of the microscale, the state of the macroscale *necessarily* follows. For instance, in the case of symmetry breaking, given the infinitesimally small flucations of the system, some macrostate follows. This may appear as arbitrary to an observer, but there is some microscale that is the case. Philosophers have thought before about supervenience and emergence. There's one notion of "brute emergence" where somehow properties come into being that *don't* supervene on the underlying properties (or states on the underlying states). A lot of people have argued that this is nonsensical - in other words, that all higher scales must supervene on lower ones. But these are great questions, because applying this to the details of our own physics has not been done yet.
All the best! Erik P Hoel