Hi!
I would recommend the Might & Magic collection, if you like som rpg and dungeon crawling. The first two are a bit to old school for me but 3 - 6 are really good. Thats 4 games that will take ages to complete:)

There is nothing really like Deus Ex on GOG because nothing is really like Deus Ex. If you want entertainment for your money then the Fallout games give you most bang for the buck. After that I would recommend Empire Earth and Arcanum. After that it comes down to person preference.

If what you want is a shooter game with a good plot, then Second Sight might be right up your alley. It's not as big or as RPG-ish as Deus Ex, but it's still fun.
Advent Rising might be more like what you're looking for, but I can't give an in-deth analysis because I have not played it myself.
On the RTS front, my personal GOG favorite would be Sacrifice, also a game with a good plot and some very... interesting visual designs.
If you don't mind trying out a space-sim, I highly recommend Freespace and Freespace 2. Again, good plot, and fantastically good space dogfights.

I would say it feels like a spiritual predecessor to Mass Effect, plus you get to fly your ship yourself [edit: only in the introduction]. Although, since I haven't played for more than half an hour or so I can't give much of an opinion.

Indeed. Especially if you're looking for overlooked gems. Another game in that category is Giants: Citizen Kabuto, which also contains RTS elements in some parts of the game.

I don't wish to spoil things for you, but you only get to fly the ship in that one opening scene, then never again. You do get to drive a Jeep-like vehicle for a little while later in the game though.

Oh well, I edited the post. I'm not bothered by spoilers, though that is a little sad, flying is fun (at least when it's fully 3D instead of that crappy 2.5D STO uses, since when is there a "down" in space?)

Duke Nukem's pretty awesome but its nothing like deus ex. You get a bunch of cool weapons and you go kill aliens. Unreal Tournament is also awesome and has bots that are pretty good so you can get alot of game time from it.

If you haven't played Psychonauts yet and enjoy platformers or games with great story and setting then this is worth grabbing.

Freespace 1 & 2...
/thread
Karl

You can try Die by the Sword. It's a completely different animal from Deus Ex, though it doesn't mean it's no good. However, like Deus Ex, there's also nothing out there that's like it - if you don't include the indie game Determinance.

Heroes of Might and Magic 3?

Yeah, you're not going to find anything like Deus Ex, unfortunately. Anywhere. Even the sequel was completely different. However, here are some GOG recommendations: Giants, Hostile Waters, Sacrifice and MDK2.

Asking for something "like Deus Ex" is like asking for something like Vampire the Masquerade: Bloodlines: neither of those games has anything resembling them.
Anyways, you asked for game recommendations so here goes:
The Fallouts...because they may have influenced Deus Ex somehow as far as deep RPG elements go.
Jagged Alliance 2...one of the few games where you can kill someone by throwing a stick of bubble gum at them if they are critically wounded :D. Slap on the good old 1.13 mod/patch and it's supposed to make JA2 THE PERFECT GAME.
Arx Fatalis might be slightly like Deus Ex as far as the FPS-style view and RPG mechanics go. However, you won't find aliens, MJ-12 or any consipracy theories in it. Fun Fact: Arkane actually pitched the game as Ultima Underworld III to EA execs but got turned down for whatever reason.
I would recommend another game close to my heart in this spot, but I think the forum regulars already know what it is and I do think they get a wee bit tired of prosyletizing about it all day, every day. Just ask them about JudasIscariot's game ...they'll know what you mean :D.
Die By the Sword is fun as well but be warned it has a weird control scheme where the buttons/mouse movement make your sword move accordingly thus allowing you to make your own custom moves. The system takes a little getting used to but it will grow on you ...like a tumor! Also, make sure to check the sticky in the DBTS forum for links to Hazzard's graphics enhancement mod for the game. Not only does the mod pretty up the game but solves any discoloring issues you may or may not have.
And if you are not sure on which game to get, why not hop over to the "Welcome Please Read" sticky and check out the demo links thread to find a demo for your prospective game? It's a list compiled by the community for the community.
Good luck, dude!