I wanted to personally confirm this.
So the way it works is that all Mons disobey, not just trades like I think it was in previous games. This stops you from going to late game areas instantly to get easily usable obedient level 60 Wugtrios, though you can still catch those (I did so. it has a Ground Tera hat and is fantastic).
To be a bit clearer on the mechanics: If you level your own Pokemon past the level cap, they won't disobey. It seems to be based on the Met At level of the Mon in the summary compared against your Gym Badge level cap. This means you don't necessarily have to beeline the Gyms just so that your Mons obey you if you're using mostly trained Mons instead of new wilds. Gym Badges are the only progression that increases the Met At level cap, though, which incentivizes you to get around to them sooner rather than later. Other types of progression have great exclusive rewards too, though. First Gym Badge gives you a level 25 cap. Oh, and the more Gym Badges you have the easier it becomes to catch Mons.
Anectodal evidence: the lvl 75 Lucario we caught which i posted in this topic, never obeyed us until we had basically cleared the game.
We also fought what I think was 3rd gym at the time (so our obedience was pretty low, i think it was still at 25).
We used 3 pokemon for it:
- Arcanine (lvl 33), caught normally as growlithe at low lvl, always obeyed with no issue
- Gardevoir (lvl 34), caught in a regular tera fight at that lvl, would disobey
- Lucario (lvl 75), would obey like once in 5 turns (enough to still oneshot the poor lvl 37 enemies though)
I kiiiinda like how they did this honestly? You arent punished for actually training your pokes, but you're prevented from just breaking the game with a lucky high lvl catch from a raid or tera den.
As far as the storylines go, the Titan one gives you the various mobility forms iirc, so probably while in theory you're free to do whatever, I think the devs kinda expect you to tackle the Titan and Gyms more or less at same time, while cleaning up the team Star bases as you find them.
Ofc that doesn't mean you can't do these in any order you want (all of the plot-relevant map areas are accessible without flying, swimming or climbing), you're actually free to tackle things in whatever order (for the joy of many players I guess).
Sadly with gyms not scaling with level, this may mean you will end up facerolling certain gyms if you opt to do things "in random order".
Oh one thing I could use confirmation on: we were not able to use X-items in story battles / gym leader fights, the game would let you use them but say they had no effect there. Potions/Revives/etc worked normally however.