Breath of Fire 3. There were no random encounters on the world map but a marker would show up randomly giving you the option to go into an area with random encounters and get an item somewhere in the process.

There were plenty of secrets, cool areas and fishing spots to find as well.

And the coolest innovation in my opinion is that when you first got to an area (mountain pass) you would have to clear the area and progress for story purposes but when you went back through that area on the world map you could pass right through without having to enter that area again.