Why does Enumerable.All return true for an empty sequence?

It's certainly not a bug. It's behaving exactly as documented:

true if every element of the source sequence passes the test in the specified predicate, or if the sequence is empty; otherwise, false.

Now you can argue about whether or not it should work that way (it seems fine to me; every element of the sequence conforms to the predicate) but the very first thing to check before you ask whether something is a bug, is the documentation. (It's the first thing to check as soon as a method behaves in a way other than what you expected.)

All requires the predicate to be true for all elements of the sequence. This is explicitly stated in the documentation. It's also the only thing that makes sense if you think of All as being like a logical "and" between the predicate's results for each element. The true you're getting out for the empty sequence is the identity element of the "and" operation. Likewise, the false you get from Any for the empty sequence is the identity for logical "or".

If you think of All as "there are no elements in the sequence that are not", this might make more sense.