Where do you get mewtwo, celibi, Lugia, lucario, and any other Legendary..

Mewtwo is a random event after you see a movie of blastoise and charizard in a dungeon ( western cave)

For celebi you need to have the friend area rewards from this wonder mails:

Please help Blaziken!
Blaziken is too scared to move!
A rescue is urgently needed!
Client: Blastoise
Objective: Find Blaziken.
Place: Sinister Woods 1F
Difficulty: D
Reward: Mobile Scarf + ?
Wonder Mail:
2?2Y PQF? 48?M
X4?8 64FR P6?W

Please help Blaziken!
Blaziken is too scared to move!
Reward upon rescue!
Client: Blastoise
Objective: Find Blaziken.
Place: Sinister Woods 2F
Difficulty: D
Reward: friend area
Wonder Mail:
2?2Y P4.? 4863
54?8 6?1R P6?W

Objective: Find Blaziken.
Place: Sinister Woods 2F
Difficulty: D
Reward: friend area
Wonder Mail:
2?2Y P4.? 4863
54?8 6?1R P6?W

Please help Blaziken!
Blaziken is too scared to move!
Please! Someone help!
Client: Blastoise
Objective: Find Blaziken.
Place: Sinister Woods 3F
Difficulty: D
Reward: friend area
Wonder Mail:
3?2Y P#X? 486M
F4?8 64SR P6?W

Please help Blaziken!
Blaziken is too scared to move!
Please! I need help!
Client: Blastoise
Objective: Find Blaziken.
Place: Sinister Woods 4F
Difficulty: D
Reward: friend area
Wonder Mail:
3?2Y P1+? 487H
34?8 6?4R P6?W

Then you can go into purity forest for celebi

For Lugia you first have to recruit moltres(mt. Blaze) zapdos(mt. Thunder) and articuno(frosty grotto). Then alakazam says you have to go to their friend area and after a short movie you can go to silver trench.

You can't recruit lucario in this game.

And all the other Pokemon are random events or you can get them already.

Mewtwo: Western Cave @99F
Mew: Buried Relic from 36BF-98BF
Celebi: Purity Forest @99F (auto)
Lugia: Silver Trench @99F
Moltres: Mt Blaze Summit @3F (go without *any* job to MT.Blaze to reach)
Articuno: Frosty Forest Center @5F (go without *any* job to Frosty Forest ot reach)
Zapdos: Mt.Thunder Summit @3F (go without *any* job to MT.Thunder to reach)
Suicune: Northwind Field @30F
Raikou: Lighting Field @30F
Entei: Fiery Field @30F
Ho-oh: Mountain Faraway @40F
Lati@s: (auto if you have Southern Island Friend Area after clearing Fallen Valley)
Regirock/ice/steel: Buried Relic in sequence @15BF @25BF @35BF
Groundon: Magma Depth @3BF (go without *any* job to Magma Cavern to reach)
Kyogre: Stormy Sea @40BF
Rayquaza: Tower Top (?) (go without *any* job to Skt Tower to reach)
Deoxys: Meteor Cave @20F

Bonsly: given as statue, appear at your base after clearing all except the 'Team' room at Makuhita Dojo
Lucario: given as statue, appear at your base after getting 15000 Rescue Point
Mr.Mime/Weavile: given as statue, appear at your base after doing rescue involve in a 99F dungeon
Munchlax: some parts of this Pokemon (portrait, normal sprite) coded in the game but inaccessible without cheat