Mmm a ver...

Podrías optar por el típico Metagross con
- Puño Meteoro
- Bola Sombra/Terremoto
- Agilidad
- Sustituto

Puedes probar varios tipos de Salamence:
1º
- Danza Dragón
- Poder Oculto Volador
- Terremoto
- Garra Dragón/Demolición/Avalancha
2º (Choice Band)
- Poder Oculto Volador
- Terremoto
- Avalancha
- Demolición
Hay muchas más opciones, pero esas son las más usadas sino me equivoco.
No le pondremos Poder Oculto Fantasma a Salamence porque tu Metagross ya tiene Bola Sombra y eso puede servirte de mucho ya que si atacan a tu Salamence con un ataque Hielo, cambias al Salamence por Metagross al cual no le hará demasiado daño.

No sé mucho sobre este pero creo que podrías ponerlo así:
-Sustituto
-Danza Espada
-Bomba Lodo
-Terremoto/Megacuerno

Está bien, aunque el HP Agua no me convence mucho la verdad. Podrías cambiarlo por Sustituto, Pantalla Luz o Púas.

Está bien el Manto Espejo, no diré que lo cambies, pero sí diré que podrías también probarlo con Tóxico o con Hipnosis. Personalmente, prefiero Tóxico.

Varias opciones:
(Salac Berry)
- Fuego Fatuo (Para reducir el ataque de algún pokémon peligroso ya que quemar es un problema de estado bastante fastidioso para el oponente)
- Paz Mental
- Psíquico
- Rayo
Este es mi Gardevoir en el Net, solo que el mío tiene Puño Hielo en lugar de Rayo.
Otra:
(Leftovers/Salac Berry)
- Paz Mental
- Hipnosis
- Come Sueños
- Rayo
Puedes optar también por cambiarle Paz Mental por Mal De Ojo, o sino por Rayo. Para que no pueda escapar y tu mientras te fortaleces con Paz Mental y si tenías poca vida te rellenas con Come Sueños. Otra posibilidad también es de este mismo ponerle...:
- Mal De Ojo
- Reflejo
- Paz Mental/Hipnosis
- Psíquico/Comesueños
Claro que para éste habría problemas, así que en todo caso quédate con el anterior xD.
Y Otra:
(Salac Berry)
- Paz Mental
- Psíquico
- Puño Hielo (No lo puse anteriormente ya que ya tienes dos Pokes con ataques de Hielo)
- Rayo
Este es el típico Gardevoir xD
Y...otra más:
(Petaya Berry/Leftovers)
- Reflejo
- Onda Trueno
- Mismodestino/Paz Mental
- Psíquico
Este último, que tenga la Velocidad a lo mínimo. Es similar al Gardevoir con Fuego Fatuo, solo que te puede servir también además de para subir tu defensa con Reflejo, para reducir la Velocidad con Onda Trueno.
Debilidades:
2 al Fuego, 2 a Tierra, 2 al Hielo. Cuidado con estos tipos.
Buenop, espero que te sirviera ^^