GOG is a one truly great site. Great games. low prizes, classy community... I just love it! However, I think there are still four games that IMHO absolutely NEED to be on the site.
The first two games are Duke Nukem 3D expansion packs Duke Caribbean: Life's a Beach http://www.youtube.com/watch?v=bkdlmWdgWJg
and Duke It Out In D.C. http://www.youtube.com/watch?v=jF7ovXkKCa0
If GOG can have Sunstorm Interactive's other Build game expansions, then why not these two? You can't find Duke Caribbean legally anywhere!. Even eBay (as for the moment of writing) has only one copy for sale and it costs 55 dollars.
The third game is Shadow Warrior. http://www.youtube.com/watch?v=30WXr8353X8 Again, another decent Build Engine game by 3DRelams that you can't find anywhere. I believe it's one of those lost underrated gems.
The fourth and final game is Carmageddon. http://www.youtube.com/watch?v=osxymgAA3p0 Crazy, violent and controversial. Truly a classic DOS racing game. Add all the extra content from the Splat Pak, and I am ready to pay good money for some oldschool car carnage!
How about you? Would you like to see these four games being added to the catalog? I certainly would!

You can purchase a direct download copy of Shadow Warrior from 3D Realm's website.

If I were to make a list of four games I wished were on the site it wouldn't include any of those, not by a mile. People are different though, that's what makes life fun.

Do those Duke expansions run in eDuke? I might uh... track them down... if they do.

Flashback, Heart of Darkness, Prince of Persia & Prince of Persia 2: The Shadow and the Flame.

I'm pretty sure they do. Remarkably, someone got them all to work in spam-filter's Mac OS X port of eDuke32.

Oh, and of course these other four.....

Wolfenstein 3D, Wolf. 3D Spear of Destiny, Doom, Doom 2, Doom 3. Well they're actually 5 :-P

KKND, yes. Fun game. Nice story (as RTSs go).
Dark Reign....was kind of "meh", but probably would go well here.
C&C1+2, and RA1 are available for free from EA's C&C site. Probably not going to appear here, even if gog do manage to score a deal with them. Would be fun though.
Dune? Dune2000? Clunky as hell. Bad UI/controls. Painful gameplay. I'd hope not.

I liked Dark Reign, it's not my favourite RTS (and I already own it + the expansion and the bad sequel, so I wouldn't buy it again), but it was very well recieved when it came out, and still has a somewhat big fan base and mod community, I think it would fit very well on GOG.
When it comes to C&C, you're right, they're available for free, even though they are somewhat complicated to get working. I'm not sure if people would be ready to pay for them just to get hassle free versions of them, and I guess it isn't in GOGs best interest to provide them for free either - but when you talk good old games and genre defining games, those are pretty hard to leave out.
When it comes to Dune, you are absolutely right about Dune II - I could never really get into that game because of it's horrible UI and strange controls, but it is an important game and should somehow be on the site, perhaps as a bundle with either the fantastic first Dune game (which was a Cryo game though, so combining games from different publishers might not work well), or with Dune 2000 - which you and many other seem to hate, but I have always loved. It's Dune II but with the C&C UI and controls, and awesome FMV's, what more could you ask for?
And don't forget Emperor: Battle for Dune. Might feel like a too new game still, but it's a 2001 title and considering there's a lot of 2003-07 games here already that shouldn't be a problem - and that's a game that hasn't been entirely problem free to get working on XP and newer OSes.
Both Dune 2000 and Emperor: Battle for Dune are games I'd certainly buy on GOG if they were to be released, I'd almost be willing to spend $9.99 on them, though $5.99 should be the better price point, especially for 2000.