Vast maps such as in Red Dead Redemptions and Skyrim are sufficient for me. They are plenty big enough to enjoy doing whatever you feel like and exploring their respective virtual worlds that can keep you at least semi-entertained for hours. Coming upon camps, cabins, new animals/creatures, etc. offers a different aspect of gameplay.

Currently enjoying the exploration of Bioshock Infinite more than the actual gameplay.
I always check every corner for lockpicks & infusions and enjoy the beatuiful crafted world.

Other than that obviously something like Skyrim or Fallout 3. Every character in a house could have a new quest for you or a nice treasure that you can steal. Tons of different locations and no matter where you go it's always worth it.

Red Dead Redemption not as much, since the map is usually rather empty (which isn't bad per se, since a desert-like area has to look empty). On the other hand it's still fun to go around and look for herbs, animals and the extremely well done random encounters.

I love to explore.

It depends on the genre and the implementation.

The obvious games that come straight to mind when exploration is mentioned are Elder Scrolls, Fallout or GTA. These sandbox games give you full, living worlds that you can truly immerse yourself in. In every area you go to there will be something that makes it worth exploring be it a quest, mission or simply an Easter egg placed there by the developers.

However, there are plenty of games that aren't pure sandboxes that have good exploration. The older Final Fantasy games, Dragon Age Origins, Bioshock and Mass Effect are examples of games that take you to a range of different areas in a relatively linear fashion, but each area has plenty of quests, gameplay and lore for the player to discover if they choose to.

Similar to this are games like Deus Ex and Dishonored where exploration is essential and the game actually gives you multiple paths to achieve the same goal. The gameplay and exploration go hand in hand with these games as exploration will often reward the player with new methods to complete a given objective.

Anyway, those are my faves.