For what it's worth, after a another day's worth of experimenting, I solved my problem by:
1. After the map successfully loads, I use a dojo.connect to tie displaying the Loading... message to the map 'onExtentChange' event. That particular event avoids needless message displays while layers are merely being turned on and off.
2. After the last dynamic layer is loaded, I use a dojo.connect to tie hiding the Loading... message to the last layer's 'onUpdate' event. Since this layer is usually the slowest to load, it's normally the last event to fire.
The tricky bit is figuring out which of the layers being loaded through a configuration file is the 'last dynamic layer', but that's another story.