I admit i almost fell off my chair laughing

You can try San Andreas, Guerrilla or oblivion

Maybe it's not exactly what you want, but Mount and Blade: Warband is aces.

For me, though, it started to drag in the endgame. It seemed sort of pointless to continue conquering new territory, as all that really accomplished was to make my empire more difficult to manage and defend. Maybe I was doing something wrong.

What about Gothic 2? It's here on GOG and isn't it a good sandbox? I haven't played it yet but might get it based on what I have read.

The Sims 3?

Xenus 2 White gold :)

Saint's Row 2 is a better GTA game than GTAIV is, if that makes any sense.

It does to me, and it should to everybody that played GTA 1 & 2.

The Scarface game was kind of nice and I had a lot of fun with Crackdown, but that's a 360 exclusive.

Hell, go oldschool, play Hunter. The game was way ahead of its time. I must admit, I don't remember if I ever completed any of the missions. I usually spent most of my time exploring the huge world and dicking around, blowing stuff up.

It sounds like you're actually looking for open world games, rather than sandbox games.

The difference is that sandbox games just give you a bunch of tools and you can do as you please with them; open world games usually involve an overarching narrative with objectives/missions which can be done in a non-specific order - basically, the opposite of a linear game.

Anyway, if that's the case, I'd suggest Far Cry 2.

Mount and blade although id go for warband great game that you can do your own journey to rule a kingdom

I agree on this recomendation!

my suggestions are try out the mafia series both mafia 1 & 2 are very similar to the gta series just the flavor is old :D
other suggestions also look out for the godfather series

Also you can consider prototype. More than a sandbox is a "do what you wanna do", is an open city and you can destroy everything.