Legendaries should be made stronger. Since you dont have the actual number for stats etc, and you have the growth rate thingy for gyms and trainer battle, i suggest you make legendaries a tougher challenge as compare to the character's current growth rate, that is no matter what level you are, legendaries will always be stronger and in the "Danger" gauge zone (maybe 20 "levels" higher in terms of ability and skills)....Also, a caught legendaries will not listen to your command until your growth rate is on par with it's level.
Let's have some new triangle instead of the boring fire/grass/water, we add dual type
Dark>Psychic>Fighting, but Grass>Water>Fire
Technically, type advantages doesn't play a big role here.
Defensive play will choose slowbro, offensive will take breloom, while houndoom for diverse movepool