Currently working on a language, I feel dizzy after reading this. My stdlib will provide a (byte) Buffer class with basic low-level methods but I feel like iterating through it in fancy ways should be the concern of the user or 3rd-party libraries. I fail to see this as part of a programming language. Am I wrong here ?
Then you can have a nice, user-friendly string class for basic UTF-8 text, which is pretty easy. Ignore sorting and grapheme clusters (those probably belong in libraries, and they require fairly large tables). Consider providing a library function to iterate over UTF-8 "characters" (as unpacked 32 bit Unicode code points).
This is one of the sweet spots in language design, and it provides enough structure for third-party libraries to work well together, without everyone reinventing their own string type.
For another good alternative to this approach, see Ruby.