After doing a deeper dive with google, I think I have the answer.
It turns out that this is a behavior defined by Java to ensure type safety.
In Java, a Set<String> is a 'Generic' collection.
Generics in Java cannot be up-cast (generics are not covariant) because (in part) Java erases the type information (of generics) upon compilation to bytecode.
There are several resources that I found that explain this:
Because a Set<String> in Apex is implemented as a Java Set<String> (using the HashSet data structure, though that bit isn't important), Apex is subject to this restriction of Java.
So why are Lists and Maps in Apex are just fine with up-casting?
I think this speaks to how Salesforce implements these two collection types.
Salesforce doesn't directly mention how Lists and Maps are implemented in the documentation (unlike the documentation for Sets), but based on how we are able to declare Lists like this
String[] stringList = new List<String>();
And access list indices like this
String result = stringList[0];
I'd have to say that I think Lists in Apex are actually Java arrays (which are covariant, and therefore can be up-cast) with some extra bits to hide the fact that Java arrays have a static size.
Maps are...I have no idea.
The following snippet works
Map<Id, String> testMap1 = new Map<Id, String>();
Map<Id, Object> testMap2 = (Map<Id, Object>)testMap1;
While this snippet won't compile
Map<Id, String> testMap1 = new Map<Id, String>();
Map<Object, String> testMap2 = (Map<Object, String>)testMap1;
The methods exposed by the Java Map interface look very similar to the Map methods that Salesforce offers. Perhaps Apex Maps end up using Java type wldcards, or are a custom implementation that stores the keys in a set, and the values in an array (and has something to map keys to indices in the values array).