...
Is that even legal for them to hold the package from me? ...
Of course it is.
No different than.... well, not gonna dig up any examples, but if Apple says it is available on xx date, then it is available on xx date. When you bought it, you agreed to it.
If you and Apple had agreed on an earlier date, then UPS would have a problem.