Although it was a while ago, I'm pretty sure I tried using the addLayer with an index (as suggested above) and found that the index value provided was used in relation to which array list the layer was included in. It didn't allow me to intermingle mapping service layers with feature layers.
That is, if I have 3 MapServiceLayers and 2 FeatureLayers, there are two arrays that are maintained in the map: layerIds and graphicsLayerIds. layerIds contains the list and order of the MapServiceLayers and graphicsLayerIds contains the list and order of the FeatureLayers. So, if the layer in the addLayer call is a MapServiceLayer, the index provided will position the layer within the layerIds array; and, if the layer is a FeatureLayer, the index provided will position the layer within the graphicsLayerIds.
During rendering, the layers listed in the layerIds array are always displayed as ordered before those found in the graphicsLayerIds are displayed on top of them, also as ordered.
Again, it's been a while so I might not be remembering this correctly; so, I apologize if my addition to this conversation is misleading or incorrect. Just trying to save you some time.
Having said all that, the suggestion to include what is currently a MapServiceLayer as a FeatureLayer instead might be workable for my particular application to allow for the desired re-ordering functionality. Really, it just depends on what other functionality I need to do with that layer and, off the top of my head, I don't remember ... but will certainly be revisiting it.
Cheers,
jtm