You don't have to reshuffle from the top all the way to the bottom. Break it up into tiers. Top 20%, reshuffle amongst themselves. Top 40-21%, reshuffle amongst themselves, etcetera. As you actually get better, you'd "graduate" to the new tier. The people already in the tier would see some new opponents that wouldn't be ridiculously easy to beat. Rather than being based an a single digit, arena rewards could add bonuses based on your tier. People would actually want to compete in the battles, rather than just hit 3 and be done because it's not worth it to be high ranked unless you're in the top 10. Make it worth it to be ranked according to your actual skill.

My other suggestion would be to NOT do the reshuffle concurrently with the Palace. Have the arena stuff be a big deal during the week and the Palace on the weekends.