I really enjoy playing DexNav trainers, but the window of opportunity is pretty small to enjoy their presence. They either steamroll me at the beginning of the game when their Pokemon are 40+ levels higher, or they get steamrolled by me when my Pokemon all out-level them later.
So a good solution might be to have their Pokemon match the highest-leveled Pokemon in your party, like the E4, or like the Rotoms you encounter in TVs.
A section where you can opt to have double-battles with them would also be super-cool if possible. It would be like a mini Battle Frontier.