RSE is best suited for Swampert, but Sceptile is better stat wise. Blaziken can also be a good choice as there are very few Fire types. So I would give teams for all the starters.
Swampert team: [Swampert / Dodrio / Slaking / Gardevoir / Hariyama / Ninetales or Ludicolo]
Blaziken team: [Blaziken / Dodrio / Slaking / Gardevoir / Ludicolo or Shiftry / Tentacruel]
Sceptile team: [Sceptile / Dodrio / Slaking / Gardevoir / Hariyama / Tentacruel]
In Swampert Team, Ninetales is the option for RS, and Ludicolo for Emerald
In Blaziken team, Ludicolo and Shiftry are options because of version exclusivity
All six are available before Gym-2 except Ninetales and Dodrio, though you can get a Lombre later (west of Fallabor town). If this is difficult for you, then you can replace Gardevoir with Manectric, with moves: Thunderbolt, Bite, Flash, whatever you want. Also you can replace Dodrio with Crobat if you don't mind friendship with moves: Fly, Wing Attack / Air Slash, Steel Wing, Shadow Ball / Giga Drain / Poison Fang or Swellow if you don't mind tons of 'mons catching very early and difficult to train [Moves: Fly, Wing Attack, Double Edge and Steel Wing]
It is advised to train Slakoth and Ralts using Exp. Share you get from Mr. Stone as soon as you deliver Devon's Goods, as they are too weak and too slow in levelling up, though their final forms are great.
Edit : Tentacool too, until it gets stab
Water types:
Swampert
Ability: Torrent
- Surf
- Dive -> Waterfall
- Mud Shot ---> Earthquake
- Ice Beam
Mudkip as starter. Dive and Waterfall are HMs and useful STAB. Ice Beam is for coverage and Earthquake is STAB, both are TMs (latter can also be learnt at level 52).
Tentacruel
Ability: Clear Body / Liquid Ooze (former preferred)
- Surf
- Dive --> Waterfall
- Sludge Bomb
- Ice Beam
Tentacool can be caught early in Dewford town wtih an Old Rod given by a fisherman. Refer the same explanations given in Swampert one.
Ludicolo
Ability: Swift Swim / Rain Dish (former preferred for In-Game)
- Ice Beam
- Surf
- Giga Drain
- Rain Dance
Lotad is available very early in the east of Petalburg Town in Sapphire and Emerald. Ice Beam is for coverage against Flying types. Surf and Giga Drain are STABs. Rain Dance to support his ability.
Grass types:
Sceptile
Ability: Overgrow
- Leaf Blade
- Giga Drain
- Dragon Claw
- Rock Tomb
Treecko as a starter. Giga Drain is for healing. Rock Tomb gives coverage. Dragon Claw for Kingdras in case you faced difficulty to beat Drake in emerald.
Shiftry
Ability: Chlorophyll / Early Bird
- Feint Attack / Thief / Shadow Ball
- Fake Out
- Sunny Day
- Solar Beam
Seedot is available in the Petalburg Woods. Nuzleaf is available in the east of Rustboro City. Choose either a weak stab or strong Shadow Ball to deal with Psychics and Ghosts. Fake Out is flinching in First Turn. Sunny Day + Solar Beam is only a good Stab for him.
Flyer - Dodrio:
Dodrio @ Shell Bell
Ability: Run Away / Early Bird (
- Fly
- Tri Attack / Uproar
- Drill Peck
- Steel Wing
Doduo is available in Safari Zone. Fly is an useful HM. Drill Peck is a decent filler + Stab. Double Edge deals Massive Damage, and there is Shell Bell to recover. Steel Wing for coverage. Better than any other bird in stats (not Dragon/Flying Altaria or Salamence, former is very slow in levelling up and latter is very late to obtain (after 8 gyms)).
Fighter:
Blaziken
Ability: Blaze
- Blaze Kick
- Sky Uppercut / Brick Break
- Rock Tomb / Rock Smash
- Bulk Up
Torchic as your starter. Blaze Kick is STAB. Sky Uppercut comes very late, so you may opt for Brick Break. Rock Tomb is decent coverage, Bulk Up is to raise Atk and Def. Rock Smash in case you don't need HM slaves.
Hariyama
Ability: Thick Fat / Guts (latter is preferred)
- Vital Throw / Brick Break
- Fake Out
- Smellingsalts / Rock Smash
- Bulk Up / Belly Drum
Makuhita is available in Granite Cave. I prefer Brick Break over Vital Spirit because of 5 more BP. Fake Out for flinching. Smelling Salts is an okay move. Rock Smash if you don't need HM Slaves. Bulk Up is you know....
Fire Types:
Ninetales
Ability: Flash Fire
- Flamethrower
- Will-O-Wisp
- Attract
- Confuse Ray
Vulpix is available at Mt. Pyre. Flamethrower is STAB, Will-O-Wisp and Confuse ray is just a filler. Attract because it doesn't have any other good moves (all are physical).
Side Kicks:
Slaking
Ability: Traunt (don't underestimate it!)
- Slack Off
- Fire Blast
- Strength / Secret Power / Return / Hyper Beam
- Shadow Ball / Aerial Ace
Slaking wynaut? Just OHKO your opponent, and then switch out to avoid Traunt! Slakoth is available in the Petalburg Woods. Slack Off to heal yourself. Fire Blast is a good coverage for the gyms and E4 in RS. Secret Power is just a good STAB with good chance of secondary effect. Strength is a high powered STAB HM move. Return's power will be high since you had levelled it up since it is level 5. Hyper Beam is just massive. Shadow Ball if you didn't use it on Shiftry or Aerial Ace for Coverage. At the starting you may find difficulty in evolving Slakoth, so you may use Exp. Share after delivering Package to Steven from Mr. Stone or something.
Gardevoir
Ability: Synchronise
- Calm Mind
- Psychic
- Thunderbolt
- Hypnosis / Future Sight / Flash
Gardevoir is the main character in your playthrough. Its Calm Mind + Psychics or Thunderbolts are very Dangerous. Ralts can be obtained in the east of Petalburg Town. Moveset is Self Explanatory, Flash in case you don't need any HM Slave.
Roxanne: Marshtomp, Grovyle, Combusken and Lombre
Brawly: Tailow and a Special attacker
Wattson: Marshtomp, Grovyle, Makuhita, Combusken (if Emerald with Combusken, try Calm Mind Kirlia)
Flannery: Marshtomp / Tentacruel / Calm Mind Gardevoir + Water Sport Lombre = Flannery crippled
Norman: Bulk Up Combusken and Hariyama
Winona: TBolt Gardevoir, Swellow for Tropius, Ice Beam for Altaria
Tate & Liza: Grass types, water types (Thunderbolt Gardevoir for Emerald only)
Wallace / Juan: Sceptile, Gardevoir, Ludicolo and Shiftry
Sidney: Blaziken and Hariyama (along with Gardevoir to void attack drop from Mightyena's intimidate)
Phoebe: Shiftry, Slaking, Swellow and Ninetales (stall)
Glacia: Gardevoir, Hariyama and Blaziken
Drake: Swampert, Tentacruel, Rain Dance-Swift Swim-Ludicolo, (Sceptile or Slaking for Kingdra in Emerald)
Steven (RS):
Skarmory: Gardevoir, Blaziken, Slaking
Cradily: Blaziken, Hariyama, Swampert
Claydol: Swampert, Sceptile, Ludicolo, Shiftry, Slaking with Shadow Ball
Armaldo: Tentacruel, Swampert
Aggron: Tentacruel, Swampert, Blaziken, Hariyama
Metagross: Slaking, Blaziken, Swampert
Wallace (E):
Wailord: Gardevoir
Tentacruel: Gardevoir
Ludicolo: Swellow
Whiscash: Sceptile, Ludicolo, Shiftry
Gyarados: Gardevoir
Milotic: Sceptile, Ludicolo, Shiftry, Gardevoir with lots of Calm Mind