My recommendations off the top of my head:
Group A - Fallout-style: role-playing more important than storyline
Fallout 2 is somewhat flawed, but certainly a must if you enjoyed the first one.
Arcanum is a good choice if you liked the two Fallouts, but it is quite rough around the edges and not very friendly towards a newcomer to the genre, I'm afraid.
(Both are here on GOG, dirt cheap.)
Group B - Bioware: storyline more important than role-playing
Both Baldur's Gate games are true classics, and well worth it.
Planescape: Torment is easily the best written game I've ever played; if your English is up to it (it's a very, very wordy game), I can't recommend it enough.
Knights of the Old Republic are excellent if you get tired of fantasy settings (and playing RPGs, that's bound to happen sooner or later). The sequel is even better, until it falls apart, as it is very unfinished.
(Bioware games have the bonus of being on the whole very user-friendly. Some are also quite easy to buy; Torment, however, is notoriously almost impossible to acquire legally for a reasonable price.)
Group C: Sandboxes
The two Gothics available here on GOG are great games, much more action oriented, with a large world where you can do what you want. Controls are clumsy at first, but you will get used to them.
The Elder Scrolls III: Morrowind is *the* sandbox RPG, and a pinnacle of this type of gameplay. One of the most free-form games you'll find.