There isn't enough data to make a blanket recommendation, so here are some things to consider. All are generalities and can be ignored if certain specifics override them, so use your judgment.
- If your employer is doing well, it is better to stay longer and get promoted from within. (Based on "Relatively good one" I'll assume this is the case.)
- If your employer reorganizes frequently, is supports the "Stick it out case."
- If your employer encourages people to find their own new jobs within the company, that is usually the best route. (This isn't always the situation. In many companies you need your current boss's blessing) Based on your explanation it seems like this isn't the case.
- If you are learning a lot, add that to the case to stay.
- If your new manager has ethical issues (as opposed to just competence issues) start your search right now. Not 30 minutes from now. Not tomorrow. Not next week. Now.
- Same if you're put on any kind of performance improvement plan (PIP). Don't think "I'm competent, I can work my way out of it". PIPs are paper trails to keep them from getting sued. Consider the duration of the PIP to be your severance.
- As you've figured out, it's rarely a good idea to go over your manager's head unless you have an outstanding relationship with the CEO or similar who would ask you later "Why didn't you come to me first?"
- If you have to leave, find a new job first. Then be professional on the way out, and don't throw your manager under the bus. Just say, "I really enjoyed working for you, a dream opportunity came up." You never know when they'll be asked for a back-door reference check on you.
- Similarly, don't badmouth your boss when you interview. (You don't want to seem like someone easily discontented.) You can say "It's now or never to leave, and I think your company has a much better future. I'd rather invest in my career there."
Good luck navigating this!