If this is for the singleplayer campaign, natures are going to be pretty negligible. 2 of the best Pokemon in FRLG (that can have relaxed nature without breeding) are Blastoise and Kadabra. Relaxed Kadabra is a tiny bit worse than neutral nature Kadabra, and Blastoise is almost completely unaffected by it. If you want Pokemon that would benefit from relaxed nature, even if they're still effectively worse than Blastoise, the best options are probably Clefable, Vaporeon, and Snorlax.
source
Blastoise @ leftovers
EVs: 100 SpA
- surf
- ice beam
- strength
- bite/rain dance
Kadabra
Ability: doesn't matter, neither are that great.
EVs: 100 Spe
- psychic
- calm mind
- shock wave/reflect
- psybeam
Clefable @ leftovers
EVs: 100 Atk
- strength/return
- calm mind
- thunderbolt/ice beam/psychic
- thunderbolt/ice beam/psychic
Vaporeon @ leftovers
EVs: 100 SpA
- surf
- ice beam
- bite/acid armor/hydro pump/rain dance
- bite/acid armor/hydro pump/rain dance
Snorlax @ leftovers
Ability: thick fat
EVs: 100 Atk
- body slam/return
- yawn
- shadow ball
- surf/brick break/earthquake
If this is for competitive 6v6 singles, your best options (that are obtainable in FRLG) are probably Blissey and Suicune.
source
source
Blissey @ leftovers
Ability: natural cure
EVs: 252 HP/252 Def/4 SpD
Relaxed nature
- thunder wave/wish
- seismic toss
- softboiled
- ice beam/thunderbolt
Suicune @ leftovers
EVs: 252 HP / 252 Def / 4 SpD
Relaxed nature
- calm mind
- surf
- rest
- ice beam/roar
