To get Relm, head to Owzer's mansion in Jidoor. Turn on the lights and examine all the pictures. One of them will open a door after a battle, leading to a dungeon. Get through this dungeon and you'll meet up with Relm, followed by a boss battle and a new magicite.

To get Strago, place Relm in your party and head to the Fanatic's Tower (you may have seen it on your way to Mobliz). Talk to Strago and he'll join you. My memory is a bit vague, so you might have to finish the Fanatic Tower quest before he joins you. I'm not sure.