I really have to second Elder Scrolls III: Morrowind. It’s very open-ended, so you can start exploring the island of Morrowind right off the bat. I have spent hundreds of hours playing this game. It is so engrossing, it is the only game I know of that has a rating of five out of five “dirty dishes”, a rating of how much a game causes you to neglect housework and other real-world obligations. I have forgotten to eat for an entire day while playing it.
Elder Scrolls IV: Oblivion is also quite good, and is very, very pretty. I would, however, recommend Morrowind over this newer title, considering that exploration is what you’re after.