Note that I am not saying that legends should be catchable. But they should be tough when you face them.
Firstly, they should be at Lv 100. Legendaries MUST be hard to beat. Make their base stats Maximum, EVs towards their best stats, and for Legends with Stats tied (or close, like a 15 base difference)) for first, this is what you could do. For offensive ties(Deoxys), 252 Spd; and 252 for the offensive stat that best matches with a movepool. For Defensive(Cresselia), Give 252 to both defensive stats. the last 4 can go to the third best stat.
Movepools can be based on their stats. Take Cresselia for example. She caould be a Barrier/Wall. Just give it Reflect, Lightscreen, and a Self healing move. the fourth move can be offensive. Then again, Do as you please with the movepool.
