I like what games like Final Fantasy VI, Chrono Trigger, and The Legend of Zelda: A Link to the Past did best, myself. For FFVI, the World of Balance is almost completely linear, as is the first part of the World of Ruin. But once you get the airship, the map is wide open and you can go anywhere and do any number of interesting things (including go straight to the final dungeon, though you'd almost certainly get your ass handed to you if you went there right away).
Chrono Trigger does pretty much exactly the same thing. At some point you can go straight to the final boss, or you can explore an incredibly open world and do a number of sidequests, with hints given to you by the old man at the End of Time.
The Legend of Zelda is a bit different. The dungeons are numbered and on your map, so it's always clear where you're "supposed" to go next, but there are plenty of rewards available for just exploring the world, and sometimes you *need* to explore the world in order to get to the next dungeon. Furthermore, if you get stuck on one dungeon, you can skip it, keep playing the game, and maybe eventually find an item that will let you solve the previous dungeon, albeit perhaps not in the way the designers intended. For instance, on my first playthrough I just couldn't solve the fifth dungeon in the Dark World. I needed a block to hold down a switch, and there was no block in sight. So after messing around for some number of hours, I give up, go to dungeon six, and what's the treasure of that dungeon? A wand that makes blocks to hold down switches! So I can then go back to dungeon five and beat it. It wasn't until probably my third or fourth playthrough that I figured out how to solve the level five puzzle without going on to level six -- for the longest time I thought that my way was the only way to do it.
So that's what I usually like best. Call them semi-open world games, if you will.