I think we should enforce this assumption (i.e., return EINVAL or something similar) instead of sorting the segments.

Thinking about this from a user's standpoint, a kldload triggering this assertion almost certainly means that something went wrong during linking or that somebody is trying to mess with the kernel.
It would make more sense to have the operation fail and let the user know that something's up instead of silently correcting the error.

Reading through the ELF specification this is not actually a requirement.
Putting them in order is the de facto standard, but I can see some obscure compiler doing whatever they want.
What would the error message say since the file is technically in-spec?

An ENOEXEC with something along the lines of "Improperly sorted segments " is fine.