Hi Theo,
> if I decide to change the order of layers in the MXD's table of contents, then share the map as a service (overwriting the existing one), the legend glitches out on the online map (the Web AppBuilder). Looking down the legend on the online map, the legend is fine up until the first layer where the order has changed.
This behavior is expected and by design. When you first publish your map doc as a map service, each layer is given a unique ID. For example, let's say you have a map with 3 layers: A, B, and C. When you publish it as a map service, (going from bottom to top in the TOC) layer A is given layer ID 0, B is given layer ID 1, and C is given layer ID 2. When you create your app in Web AppBuilder and start to configure widgets, the widgets will read and work with the layer IDs assigned in the map service.
If you change the order of your layers in the map doc, then re-publish it, the layer IDs of each layer will also change. So when you re-open the web map in the Web AppBuilder app (built on the previous web map) - the widgets may not display the correct information. You will have to create a new app, which would reference the new layer IDs.
In ArcMap 10.3, we introduced a feature in the Data Frame properties General tab. There is a checkbox "Allow assignment of unique numeric IDs for map service publishing" that will address this "issue". If you check this checkbox BEFORE you publish the map as a map service the first time, then the workflow you describe will be supported.
Hope this helps,