I remember similar words being said about Crimson Skies. I mean, check that shit out. Compatibility aside, my phone could run that without problems.

I agree. That is why I don't install those mods that let me have higher resolutions. I like playing old games old school style.

Deus Ex. If you like Deus Ex: Human Revolution, you'll like the first one as well. They feel pretty similar, gameplay wise. And the story is really good.

Because of the nostalgia element, I suppose I can only point out games that I have discovered on GOG that have really impressed me. From this perspective I'd have to argue that they have aged well. Top 3 would be:

Psychonauts
Sanitarium
Syberia 1&2

I think that it would be easier if we list the games that do not have aged well.

A lot of games that I think didn't age well come from the early true 3D era of PC games. The graphics kind of sucked in a way that really does impact gameplay. Or maybe it's just because everyone was remaking their 2D games as 3D and the transition didn't always go well...

Btw, I have a hard time thinking of games newer than 2000 as being "old". But I do realise it's 2013 now so I should probably adjust to that.

Well, BG1 at least hugely benefit from higher resolutions since the orignal 640x480 (or was it 800x600?) resolution looks rather pixelated on a modern monitor.
Personally I prefer not to overdo it, but play them on something like 1280x1024.

Too right! The ones with fake 3D look still pretty ok, like Dungeon Master or Duke Nukem 3d

Being old enough to have seen that change happen in real time, it is even worse than that. Back then , those early true 3D games were a real revolution in gameplay. Red Baron or Aces over the Pacific for flight sims, Wing Commander 3 for space shooters, Midwinter for action games actually made the previous generation not only obsolete but ridiculously unrealistic. The leap forward, at the time, seemed huge Playing these games now totally changes ( or challenges) our perception of that leap. Nowadays, WC3 looks barely less obsolete than WC2.

Whew... I was getting worried that nobody would mention Deus Ex. Honestly, it took 48 posts for someone to say it!?
I just finished playing it for about the 30th time, and I still think it is amazing. I still find new ways to play it, and find different solutions and outcomes to most situations.

Echoing a few more that have been mentioned - Blood and Descent. I had played demos of these back when they came out. I had pretty much forgotten what they were like. I finally played the full games 2 years ago, and had an absolute blast.
System Shock 2 - Again, had only played a demo about 10 years ago. I had hyped up this game so much over the years, I was worried that it would be a let down if I ever played the full game. It was even better than I imagined.
Giants: Citizen Kabuto - Remains fresh. I have never played an FPS even remotely similar to it.

A couple that I haven't seen mentioned here yet...
Tropico - Bought it randomly. I've probably had more fun with this than any managerial sim (except maybe Evil Genius.) It has the perfect level of management for me. I don't want to manage a massive city of one million people, and micro-managing every single citizen/employee can be a bit much for me. Tropico fits perfectly in-between.
Medal of Honor: Allied Assault - IMO, one of, if not the best straight-action military shooter. Expansions are great too.

edit - sorry if I don't make much sense. I am posting under the influence of some new medications, and am feeling a bit wonky. It took me an hour to write this post.

Just some of my personal favs:

Descent 1&2 - restoration projects be damned; I actually prefer the original versions. still a blast
MoO 2 - still a great game all around even if diplomacy doesn't require much strategy
Rollercoaster Tycoon 2 - simply because I prefer some of the changes made since the first game
Stronghold - it's hard for me to believe this is already twelve years old; hasn't lost any of its charm or fun
King of Dragon Pass - without GOG I don't think I'd ever have known about this gem

There's bound to be plenty of other GOGs I haven't considered yet, as my backlog is still rather immense.

Games are timeless and don't age. Now go play one.

The only exception I've made to that was the original descent - my monitor really didn't like the original low resolution.

I recently played Ultima I for the first time ever. It had ugly graphics and very illogical gameplay, yet for some reason I still felt drawn in and loved grinding dungeons to level up.

Currently at Ultima II, but I don't feel the same connection there...

Just picked up Perimeter and I'm amazed not only by how good it looks, but by how sophisticated the code is for some of the routines. The energy bubble effect is especially good, geometrically speaking.

Some of the style-heavy games still look great, like the Oddworld titles, MDK, Giants, and Undying. And a lot of the RTS titles have matured just fine, since they were designed to do a lot with a few pixels to begin with.