In my opinion, you only need three things for harder/better balanced/more engaging battles: restrict bag usage, level parity, and competitive move builds.
You want to treat the battle as a puzzle and your party as the pieces by which you solve it. Using items is like cheating the puzzle, and having higher leveled Pokémon sucks the fun out. And if you're going to use Pokémon with coverage moves and TMs, why shouldn't your opponent?
I prefer soft level caps but I think most people prefer dynamically raising trainer levels instead.
I'm working on a "more challenging" rom hack too and I'm excited to make it as hard as I can and still have it be fair/beatable!
Oh yeah, and trainers should have interesting thematic teams. Give them a fun core concept to their team. Something memorable that makes the player go, "Wow, that's awesome!" Like giving an electric type trainer a bunch of volt absorb Pokémon with parabolic charge and double battle you. And then limit which ground type Pokémon are available, force them to think about how they're going to manage (without using the easy cop out of type immunity) Give some niche Pokémon heal block, or let them find a Pokémon with both parabolic charge and imprison. Give less interesting Pokémon a new purpose by making them the solution to the "puzzle" and reward the player for exploring and trying new/underused Pokémon out.