Elder Scrolls III: Morrowind (with the expansions Blood moon and Tribunal) seems like an obvious choice.

Gothic is pretty story driven a bit sandboxy. Gothic 2 and 3 are as well, but aren't quite the amazing game Gothic was.

Fallout 3 gets pretty big once you add all the DLC and start doing the mod thing.

Arcanum is a very flexible game, as RPGs go.

Most of the AD&D titles on GOG are pretty long, some are linear though.

The Might and Magic 6 pack here on GOG is enormous, as in, you could spend all year playing through all of it, unless you have 10 hours/day to game.

The latest mod for it is almost due too. Add to that the better bodies, better heads and the like along with GCD and it's a fine choice.

RPG Classics on GOG include Balder's Gate and Planetscape Torrment that might meet your fancy

Take a gander at the Realms of Arkania trilogy.

The first, Blade of Destiny, is a creaky old thing with crappy sound a horrible interface and gameplay that will suck you in if you give it a chance. There is a huge amount of detail in character generation and the development of your hero types and freedom to explore. If you use the clue book to guide you it is actually not that long a game and the subsequent games are much improved, visually and playability-wise.

Plus you get to import your heroes from game to game.

Thank you everyone for your speedy reply! Never imagined I'd get so many helpful answers. You rock! :)

Just a couple of quick questions, if I may:

About the Might and Magic games:
Do they give youa pre-created party on startup? I ask since whenever I tried my hand at doing that in the past, I ended up forming an inadequate party...

About Realms of Arkania:
Are they from The Dark Eye rulebook, like the recent Drakensang games? Are those any good?

Thank you once again, guys! Cheers!

Might and Magic's old enough so there should be many hundreds of guides to help you create the perfect party, if that's a potential detriment :D

If you are a TES fan, definitely play Morrowind, if you haven't already. Two Worlds and Gothic 3 (make sure you get the community patch for this one) are both sandboxy games you might like.

Oh, and Divine Divinity should be mentioned, just because it's so great. That one feels like Diablo meets Ultima 7.

One more thing, since you're a fan of Oblivion. Check out the Nehrim total conversion mod. It's excellent.

One thing to be careful with if you go with Morrowind is the difference between it and Oblivion. It is much, much slower paced and has far less direction than Oblivion does. That may be to your liking, but I found it a hard adjustment. Also, the combat is somewhat different in that not all swings of your knife/sword/axe/spear will make contact. There is some weird behind the scenes dice roll thing going on and can be offputting your first time.

Other than that, there isn't much wrong with the game. Its setting is a bit more interesting than Oblivion's and the music is incredibly awesome. Of course, I couldn't tell you much more than that, because despite the fact that I have many times tried, I always find it difficult to get into Morrowind. Part of that might be because the game is a bit more difficult than Oblivion and a balls-out approach is rarely the best approach, at least early on.

As for Realms of Arkania... That game is really hard. It takes a long time to wrap your head around it. Again though, I have never played much of it. Even though I want to, I can't seem to get my brain focused enough to learn the game enough to enjoy. But if you like complicated games and you don't mind learning, I see no reason not to suggest it. It seems like it would be a really great game once you get past all the complications.

But don't take me as the final say-so. I just wanted to put in my two cents.

I know the first 5 come with pre-generated parties, but I don't remember if 6 and 7 do. As a matter of fact, the characters that are pre-generated in the early games became actual NPCs or heroes in later MM/HoMM games.

If someone doesn't like how party and stat gen works in an old RPG, I only have one thing to say to them: "trainer". I don't really use them, but there's no reason not to if it increases your enjoyment of the gameplay.

Try the Oblivion mod Nehrim. It makes the game Gothic 4.

Two Worlds is great (can't speak for the sequel, yet) once it's all patched up. I also recommend the community-developed mod/plugin frontend, called the "Two Worlds Control Panel". It allows you to download mods and plugins and install them on-the-fly, as long as they've been uploaded to the insidetwoworlds.com database. You can also manage other mods you've already installed from this frontend as well.

[url=http://www.uesp.net/wiki/Arena:Files]The Elderscrolls: Arena[/url], insanely big covers the entire world of tamriel and its a lot of fun. link to file thats ready made with dosbox built in the install and fully patched to work in windows. a ton of stuff is randomly generated so its a lot of fun ^_^
Two Worlds, open
Risen, open
Arcania, open
The Witcher, open'sih
Borderlands, open
Hellgate: London, linear and open at the same time
Dungeon Siege II, linear but long as hell
Dungeon Siege I, Linear but 2 is far better
Titans Quest: Immortal Throne, linear but longer then hell is deep and hot
Red Dead Redemption, open and insanely addictive, plus undead nightmare is very fun!
Fallout 3 GOTY ((super highly recommend, and very open))
Planescape: Torment, Long sorta open AMAZING story
NWN collection here, Linear but long and fun
NWN2, long very fun but linear
Baulders gate 1,2 insanly long and very good story, but Linearish and big learning curve at first.
Icewind Dale 1,2 personal favorites of mine, but im a masochist ^_^

Less fantasy and more shootish are the core games:
S.T.A.L.K.E.R. Call of Pripyat and Shadow of Chernobyl get the "Complete" mods for each and you have some outstanding games
Less fantasy and more shootish are the core games
GTA IV, open huge
Saints Row 2, open better than GTA imo
Just Cause 2, open and more fun then above...

if you like open world singleplayer space i can only recommend 1 series...

The X Universe....
X: beyond the Frontier
X: tension
X: Gold (the above 2)
X2: The Threat
X3: Reunion
X3: Terran Conflict

The first 2 are DRM free at Gamers Gate right now. or you can get the X Superbox.