I've been talking about this game a lot lately, but Breath of Fire 3 has one of the overworld maps I fondly remember the most.

Aside from the music, there's a lot of attention to detail. The fishing spots are indicated by a fish flopping out of the water, and the environment is otherwise alive. Even if a city is just indicated by a few buildings, you'll still see smoke coming out of a chimney or windmills spinning on the world map to show that it's a bustling place. Or you'll occasionally run into a hidden location just called "?" which you can explore to find hidden treasure or dragon chrysm.

Contrasted to that, I feel like I play a lot more games where there's just an overworld map that is overwhelmingly green on green, with the occasional desert. Even then, I still like having the option to explore the overworld map to get a sense of the world, even if there's less detail.

It's also a bonus when a game has an in-game reason for why you can't go a certain direction, like volcano spillage, instead of a message popping up saying "looks like we shouldn't go this way".

When I think of an old game, overworld map music will sometimes come to mind first since you hear it so often. It's the soundtrack to your character's journey.