With Altaria you can both use it as a physical attacker, or a special attacker. Either way, the second stat to EV train would be speed. Meaning Relaxed is not exactly a preferred nature, as it is -speed. Excluding the nature, I would EV train attack or special attack, and speed.
I would try and run a bulky set, It probably won't work well unless you get the reverse mode changed (defense + hp)