Melanurus tends to be one of the more aggressive Halichoeres. I'd add it last or at the same time as the other Halichoeres.
Look into:
Halichoeres biocellatus
Halichoeres cosmetus
Halichoeres timorensis
Halichoeres iridis
Halichoeres chrysus
Halichoeres leucoxanthus
Halichoeres marginatus
Halichoeres rubricephalus
Avoid:
Halichoeres bivittatus
Halichoeres chloropterus
Halichoeres cyanocephalus
Halichoeres hortulanus
Halichoeres radiatus
Halichoeres garnoti
All of these are nice and colorful, and tend to be at least a little more laid back than H. melanurus. They should do fine if added at the same time or before the melanurus.
As far as non-Halichoeres wrasses, any other sand sleepers (Macropharyngodon, Anampses, and Pseudojuloides) should be added before a melanurus.
Rock and crevice sleeping wrasses (Cirrhilabrus, Paracheilinus, Wetmorella, Pseudocheilinops) can go in pretty much whenever, though I would still try not to add any after an adult melanurus has become well-established in a tank.