This game you're making is basically a Japanese style tactical RPG, right? If so, I think there's a very clear model to follow. Elaborate tactical combat and dungeon exploration are diametrically opposite activities; the former is about utilising resources well and defeating the opponent quickly and efficiently, while the latter is about combing through an area meticulously to map areas expose secrets and hidden routes. They don't match. So to make a good tactical RPG, the correct notion is to have a small number of hand-crafted tactical encounters as the main meat of the game, in which case there is no need for an elaborate, explorable world map or dungeons. In Valkyrie Chronciles, the best tactical RPG in a decade, there are battle maps that are already the size of a small dungeon. A "world" beyond this would be superfluous and actually probably harmful.
Random encounters, in and of themselves, are viable when they are very quick and result in resource depletion while inside a dungeon. This works best when the dungeon is elaborate and fun to explore and the random encounters are fairly numerous and very brief, ideally less than a minue in length so as not to distract from the dungeon spelunking too much. For combat to be that quick, you really don't have time for tactical movement of multiple unitls - it only really works with blobber combat or action RPGs, which reduces the amount of time a single fight takes. In a tactical RPG, a quality encounter could be expected to take half an hour or even an hour, in which case as much as possible of the content should be unique and hand-crafted, as repeating "random" encounters becomes stale and tiresome. Random encounters have merit in Japanese TRPGs as a failsafe to allow grinding to prevent the game from becoming unwinnable and to allow players to build interesting teams. Beyond this point, there is not much point in having them, which is why many games in the genre disemphasise them as much as possible.
For movement in the world, a map with nodes like in Final Fantasy Tactics is not only sufficient, but preferable, because what you really want is to move from one tactical encounter to the other. Valkyrie Chronicles, the best tactical RPG in this decade, doesn't even have a map; you select missions from a scrapbook. The ideal thing, really, is to concentrate on are interesting, varied combat areas with interesting hand-crafted encounters, and have as little as possible of everything else.
