I don't believe you can do this. The reason being that MySite's are actually two SETS of site collections. The "My" site collection holds everything that isn't personalised. It still works if you don't allow personal MySites.
All of the personal sites are collections in their own rights but ones over which you have little or no control. You have no control over their templates for example, they are all created the way Microsoft wants them not how you want them!
So you can do what you want to the non-personalised part very easily but it is then extremely confusing to users because they go in and out of that - as they do, their menus and formatting will change. I did try this with our tenancy but I soon went back to the standard layout even though it is different to all of our other sites.
I would see about using the Managed Metadata Navigation feature in SharePoint 2013. It might require a custom server control or web part to accomplish but that would be about the only way I can think of to make them all the same without manually maintaining them on an individual basis.
You might be able to accomplish the separate sites with "pinning" or "reusing" term sets along with the managed navigation feature.