So they both have 55k HP; Omega is weak to Bolt, Water, and Earth but will null Bio, Gravity, and halve Wind. He can be Stopped as you've seen, but it's tough to land due to his high level of 119. If you still have Aeris, then Seal Evil is a guaranteed Stop that can be useful here, or perhaps combining Stop with MP Turbo for a better chance (more stars = higher chance). Stop + Quadra Magic can also be a good one if you have it though it'll only be good for a couple of casts.
Shinryu is weak to Wind only, and absorbs Holy. He nulls Gravity & Earth, and halves Bio (he can be poisoned which should be handy as it'll deal 1/32 of his MaxHP per tick). He can also be Slowed which should be done early though this also slows down the rate that poison ticks at.
Both bosses are relatively slow at 76 and 87 speed so if you have a party with fairly high Dex then you can get a nice turn advantage. However, Omega will always counter-attack when struck by an ability and Shinryu will use certain one-off abilities when his HP falls below a certain mark so you'll still need to be careful not to get overwhelmed. Omega counters pretty much anything, so you can avoid taking some damage by avoiding him but Shinryu will also attack Omega which triggers those counters.
There's a lot of nasty attacks flying around so deciding what to guard against will be important. Fire is a good one as it covers two of Omega's attacks, or Holy as Shinryu's biggest attack, Almagest, carries this element. Shoot, Cut, and Hit elements are used frequently by Omega so Armour/Accessories that reduce these are also worth considering. For status ailments, Petrify is used by both bosses so that would be a good one; Confusion and Silence as well so you don't lose a character's input at a crucial time.
So first thing to decide is whether to deal with Shinryu first or deal with Omega first and this may depend on what death counter you want to deal with; when Shinryu dies he'll use Almagest which is a heavy-hitting Holy element attack if Omega is still alive (but will also have used other nasty attacks while his HP falls, such as Lv?? Old which reduces a character's stats to 0 and Zombie Breath which prevents reviving except through the Phoenix summon). Omega, on the other hand, will use Encircle which renders one character inactive for the rest of the battle so you'd only have two characters to finish off Shinryu.
I think what people tend to do is keep Omega locked down with Stop as best they can, deal with Shinryu, and then mop up Omega but may be wrong about that.
To start, I'd try to Slow & Poison Shinryu, and land Stop on Omega with an MP Turbo Stop, Quadra Magic Stop, or Aeris' Seal Evil if that's available. While Omega is stopped, he can't counter-attack at all so that'd be the time to start hitting him with Bolt, Water, and Earth attacks. You can tie these to physical attacks with Elemental, or use weapons with those elements already aspected to them (Cid should have a bunch of these) or just stick with spells like Break.
I'd maybe be wary about committing all 3 characters to attack when dealing with Omega, as his Stop may wear off and you'll suddenly be facing 2-3 counter-attacks + any turns Shinryu or Omega get while that happens. Try attacking with one at a time so the other two can deal with any consequences that come back. You can probably be aggressive when Stop is freshly applied, but after some turns I'd maybe start to hold back a bit.
There's a few things to note with Shinryu as well. First of all, he'll counter limit breaks with Lv?? Flare so be careful about using those against him. At certain HP increments he'll use a special ability: At 4/5s, he'll use Big Guard (you'll want to dispel that ASAP). At 3/5s, he'll use Zombie Breath which renders any character that is KO'd from that point on unable to be revived except through the use of the Phoenix Summon. At 2/5s. he'll use Lv?? Old which reduces the Strength, Magic, Defence, and Magic Defence of one character to 0 (while this can be cleared by KOing and then reviving the character, remember that the Zombie Breath effect is in play by this point). And finally, at 1/5 he'll use Maelstrom which reduces a party member's HP to 1. When he dies, and if Omega is not dead, he'll use Almagest so make sure you're topped up and got MBarrier or Shield up before finishing him off (Sense should work on both of these guys if the .exe is patched so you can track when they're about to die).
Hope that helps.
