Put Magus in your party and head over to 600 A.D., Ozzie's Fort. It's to the east of Magus's Lair.
Walk in and Magus and Ozzie will talk. Go up to the next area.
In here you fight Flea, who's actually a really easy fight. Just hit with physical attacks until you win.
Go up to the next area, and ha ha, the joke's on Ozzie. Keep going up and you'll fight Slash, another really easy fight, just use physical attacks, then with that done, head up.
Don't step under the falling blade (tempting as it might be), and head for the exit. BEFORE leaving this room, there's a secret passage if you go straight down from where the stairs are. In here you get Magus's best stuff. There's also a tab in here, don't miss it. Then you can get the treasure in the chest that the blade was guarding.
Now you'll want to prepare for a boss battle. It's good to put Robo in your party, and Ayla's a good second character, followed by Magus. Equip everybody with flame absorbing/reducing armor. When you're ready, exit north.
DON'T touch Ozzie while all three are there, or you'll get a nasty counterattack. Keep HP above 250. Charm both Slash and Flea until you get Slasher 2 and Flea Vest. I suggest you keep hitting Slash with physical attacks until he's done for, then go for Flea (it'll probably run away), and finally attack Ozzie. Ozzie will do nothing once his henchmen are gone. You can (but probably don't want to) Charm him, and you get OzziePants. OzziePants is a helm that casts Chaos on you as well as HP down. Worthless.
Get the chests, then exit north as usual, with Magus in your party. Go up and when the fight comes, hit the switch behind Ozzie, of course. Then go up again, and watch the scene.
Now if you go to Medina in 1000 A.D., everyone's nice to you.