Async serial connections rely on accurate timing synchronisation to work properly, and any errors are most likely to occur on the very first character transmitted on an idle connection. It may be that the host is glitching on the very first character received and then recovering. I would expect that to cause the first character to be missed or corrupted rather than repeated, but how it's handled is up to the client OS and application. The fact you see the same behaviour regardless of how the output characters are generated makes me conclude that it's nothing to do with the Arduino output formatting logic, and it seems pretty unlikely that there's a flaw in the logic that handles the serial output buffer and also pretty unlikely that there is a hardware design flaw. More likely IMO that the problem is occurring at the client. So get another client and see whether the problem is consistent, and try different serial port speeds and see whether that makes any difference. If the problem is a speed mismatch between the host and slave then it could easily be specific to certain speeds.