TWRoO on 22 July 2009
Star Fox Adventures (assuming you have a GC controller for the Wii)
If exploring is the main pull of a game (ie not interested in completing objectives and such) then you can't go wrong with Endless Ocean. You swim around by holding B and pointing where you want to go, and interact with A.
Okami has a lot to explore too.
