Oh, the first code unit of each code point, not the first code unit of the text. That's how I had originally understood you until I got confused by the talk of byte order.
I have to say I really don't see the value of being byte-order flexible, but always requiring the header be in the "first" byte, because that makes it so big-endian and little-endian formats are packed completely differently. 2 and 4 byte code units will be misaligned all the time too, might as well just use a series of bytes in fixed order.
> What do you mean by variable width?
Make the first byte be like UTF-8 (so a prefix of 0, 10, 110, or 1110), and the following bytes be raw data. It compacts a lot better than a fixed-length header, with roughly the same level of complexity.
But now that I think about it a continuation bit is probably the best option here because it regains some ability to self-synchronize.