You know, previously I used to say "i hate it but i really don't know what else to do" but you know, i totally do now. You can:
a) do like some western RPGs where you have a sandboxy world that you can find *something* appropriate to your experience level with only a small number of areas with random encounters (eg, fallout)
b) set the encounter rate at low, make the enemies hard and allow quests to provide most of the experience
c) have a wandering monster thing like in FFXII, only you could expect to only *just* be able to kill monsters in areas which you've gotten up to, and set experience gains to high so you quickly change in ability in a new area. This opens up much more opportunity for tactical and challenging game play, and wandering around areas that you've completed doesn't become a chore because you can ignore/massacre the monsters.
at the very, very least if you're going to have random battles, have the enemies 'run away' if you're too high a level for them to provide a meaningful challenge, with the option of 'giving chase' - with MINIMAL interruption of exploring.
nothing annoys me more than going into a random battle and spending more time in the loading and winning screen than the battle itself - which happens a LOT in certain RPGs.