Really, it's not even random access per se that takes linear time, but random access indexed by code points. You can access the middle of a UTF-8 string just fine if you index by byte position. (Or more generally, by code units for UTF-16.)