During the sign-up process for a new service, LastPass offers the option to generate a password based on a few options (capitalization, special characters, etc) however, it assumes the user always wants to manually enter a username (when different from email address).
For the username generation, we can simply reuse the password generator and limit to alphanumeric characters and optionally allow basic characters (e.g., the ones enclosed in square brackets [.-_]). Additional helpful options may include: all lowercase characters and force start with a letter. This way, a new user to a website will have an automatically generated username if they do not wish their identity to be used site after site.
The alternative to this is for websites that do not allow usernames. In those situations, a far fetched although privacy friendly solution, would be to integrate with AnonAddy or allow the user to provide an AnonAddy alias they wish (as I did to create this account).
Either way, the user can either automatically generate a random username or use an fresh new AnonAddy email alias that shields their identity for every new sign-up.