Ultima series is pretty good, although the first three games are very different from what it becomes. The game worlds are very well fleshed out and it is a lot of fun to explore them. I recommend all of them up to the 8th game. Ultima 8 had a huge change in tone and gameplay, much for the worse. But even it has a lot of interesting places and NPCs; and the magic system is pretty neat. The Ultima Underworld games are also very well made, although they play very differently.
Fallout has been mentioned, but it bears repeating. Many of the game's problems and quests have several solutions and the game rewards you for paying attention, exploring the world and trying different builds. Some people don't like that the main quest of the game is timed, but I think it actually makes the game better.
Quest for Glory series mix RPG with Adventure gameplay. Mind you, both genres are very related, I think, but by doing so explicitly, and expertly, Quest for Glory manages to create very interesting gameworlds. In these games, you get to choose a class and your abilities will be very different depending on whether you are a wizard, a thief or a warrior (and later on, a paladin). I recommend playing through the original versions of QfG1 and QfG2, since they used a parser instead of an action system (look, take, use, etc). The Heroine's Quest game (which is free) is a very well made game in the same vein and definitely worth playing.
Daggerfall is the second "The Elder Scrolls" game. This game gives you an enormous swath of options making and playing your character. You can create your own custom class during character creation, with the possibility of choosing from several bonuses and penalties, which increase and reduce (respectively) how much XP you need to advance a level. There is a complex guild system where you can get access to several powerful services, such as the spellmaker (which allows you to create your own spells) and trainers (who can train your skills for gold). Daggerfall is an ambitious project that probably didn't manage to deliver half of what it wanted to do. Although the game is huge (there are hundreds of cities you can visit), it also gets very repetitive (most of the game was generated randomly, although the maps are static, the layout doesn't get regenerated). While it has other flaws as well, it is definitely worth a couple of plays!
Gothic is a game series that focuses on exploration, and reward the player for going out of his way to explore the world. The character system is a bit basic and the game can become monotonous at times, but it is still a very good series. Risen was made by the same devs and follows a very similar style to Gothic, by the way.
There are many AD&D games from SSI that are worth playing, like the so called "gold box" titles. One I think should be mentioned is the Dark Sun game (and its sequel, Dark Sun 2). They are easy to play and just follow through and while the exploration aspect of the game suffers sometimes, it is still a very fun game to mess around with.