Shadowman is a great exploration/backtracking adventure game. If you have a dreamcast, PC or N64 I highly recommend it.

If you want a giant world to explore then any of the GTA games would work, you could try Mercenaries but their is a newer one coming out this year. Another game with a massive world is Just Cause but there is another one in the works, i'm not sure when its coming out.

 agree in that one, but there is no action in the game, though i like it

Judging by your game collection, you dont have Banjo Tooie, it seemes like a good choice, Big worlds and tons of exploration, and many puzzles, otherwise Endless Ocean

It appears you also don't have Phantom Hourglass on the DS, for someone who is obviously a Zelda fan this sticks out like a sore thumb! You're also a big Metroid fan so I highly suggest you get Castlevania Symphony of the Night. It's not as good as Super Metroid but it's well worth playing none the less. Also, when you think you cleared the game, you are in fact only half way through ;) Remember that....

Dragon Quest VIII is pretty free-roaming, though it has its fair share of random encounters as well. Approach with caution, particularly if you're not in the mood for a standard RPG with a fair amount of luck involved.

Pretty much every Zelda and Elder Scrolls game to be ever released

can't get much more bored than that either...but good answer. Isn't there no way to die in that game.

OT: Drake's Fortune, Oblivion has some, Assassin's Creed, umm can't think of any more right now.

 I have all of those games.