Sounds like a bug in your template. To confirm if that is the case please see if the same thing happens when you use one of the default joomla templates.

If this is a template issue... most templates are based on Protostar and I also saw these messages on a template based on beez3, ja_builder and a template built from scratch.
Besides that I don't know how to reproduce it because it doesn't happen all the time and I sure would like to know why this happens.

Why is it displaying this sort of message in the first place? Unless I've just not followed J3.8 and users can now install extensions from the frontend, this shouldn't be there.

I don't believe it's template related to be honest

The only thing I can think of is having shared sessions enabled and navigating the frontend at the same time the post-extension install redirect happens so the frontend gets the stuff out of the message queue before the backend does. And short of internally refactoring the message queue to differentiate messages between apps, that one can't be fixed.

The template was just a default suggestion as it is the cause of so much weirdness.

Michael's comment seems to be logical IF @postkat has shared sessions enabled in global config. Do you?

On at least one of the websites I saw the message today, shared sessions is not enabled.

Does it only show the sh404SEF installation message, or does it display other extensions too? If only the one, then perhaps see if you're using the latest version of sh404SEF and/or try contacting the developer.

Looks for me like some sort of admin-plugin which is triggered onContentBeforDisplay but not restricted to $app->isAdmin.

None of those are plugin generated messages. Actually, the messages are added to the message queue from core library classes (one the installer library and the other the updater library). Still, unless someone built a frontend facing component for extensions management, a frontend request wouldn't trigger code executing those paths. Even a third party system like Watchful or myJoomla which can do management tasks remotely wouldn't cause them to display on the frontend because messages are enqueued to the user's session, and the requests from their systems would have a unique user session.

So there are three legitimate possibilities here why the messages would display on frontend:

1. A frontend extension manager component
2. Shared sessions and the user navigating to the frontend at almost the literal same millisecond as the extension maintenance task completes (well, somewhere in the short timeframe (still milliseconds generally) between when the message is queued and when it would be read out of the queue after the redirect)
3. A plugin triggering extension management actions on the frontend (core doesn't have such a feature, the closest you might get to one of these messages being shown is if the site couldn't reach the core update server when checking if the update email needs to be sent but any URL in the message would point to joomla.org in that scenario)

I have no sloution and I did not say that these messages are generated by a plugin but that they are somehow injected into the frontend.
When the effect is on all sites which are maintained by @postcat, there must be something which is installed on all these websites. Or it must be something on his server if they all are on the same server. I think that there is not enough Information.

@postkat can yo give please more Information as mentioned above?

I think I may have found the plugin causing it: Admin Forever.
This plugin is installed and enabled on most websites. I have changed the access settings to special and time will tell if this is the offender.

Thanks for updating. I am going to close this at this time

The problem remains.

Setting access level of Admin Forever to special or superuser did not help.
I am still getting messages and I have no idea if website visitor see these messages too...