I have ranted for long hours go friends about the insanity of Python 3's text model before. It's mostly the blind leading the blind.
Is this not the only thing you can really do? If strings could hold invalid unicode then they effectively become bytes and you now have to be wary of every possible string. I would rather Python just do away with strings entirely in the integration points with the OS and make you either keep them as opaque bytes or decode them.
> behaves like a string and supports all the handy string operations but which handles invalid data gracefully
Unless Guido was feeling particularly practical I can't imagine this ever making it into the stdlib because the choice of "gracefully" is somewhat arbitrary and application dependent.
Like, the changes Python 3 made were honestly pretty subtle, and nearly 15 years later there's still people reluctant to upgrade. If they broke string indexing I'm pretty sure Python 3 adoption would make Perl 6 uptake look impressive.
So, only build the index for random access if needed. Optimize "advance one glyph" and "back up one glyph" expressed as indexing, and you'll get most of the frequently used cases. Have the "index" functions that return a string index return an opaque type that's a byte index. Attempting to convert that to an integer forces creation of the string index.
This preserves the user visible semantics but keeps performance.
PyPy does something like this.
Not allowing strings to represent invalid Unicode is also a huge mistake (and essentially forced by the representation strategy that they adopted). It forces any programmer who wants to robustly handle potentially invalid string data to use byte vectors instead. Which is exactly what they did with OS paths, but that's far from the only place you can get invalid strings. You can get invalid strings almost anywhere! Worse, since it's incredibly inconvenient to work with byte vectors when you want to do stringlike stuff, no one does it unless forced to, so this design choice effectively guarantees that all Python code that works with strings will blow up if it encounters anything invalid—which is a very common occurrence.
If only there was a type that behaves like a string and supports all the handy string operations but which handles invalid data gracefully. Then you could write robust string code conveniently. But at that point, you should just make that the standard string type! This isn't hypothetical, it's exactly how Burnt Sushi's bstr type [1] works in Rust and how the standard String type works in Julia.
[1] https://github.com/BurntSushi/bstr