This is my list of "games that I've played that are fun to me, that would maybe be fun to TAS". It's a long post but I have yet to see a nice checklist of sorts.
Rise of The Triad
^not on the list but I think it's TAS-worthy. The shareware levels are different from the full-version's levels.
Crusader (any of them)
^another one I used to play A LOT. I had no remorse, since no regret wasn't in our stores. I LOVED setting people on fire and melting them with that one gun. Also kinda hard towards the end (who knew that shooting a pipe with the laser rifle would bounce off and kill myself -_-)
D-Zone
^A game I used to play wayyy back when. Was kinda fun. I don't see it on wikipedia, so it must not have been widely known. Gameplay is: You pilot a triangle, and you have a team of 3 triangles, and you must kill your opponent's team, or destroy their base core thingy. 17 years ago, I had a lot of fun in this game, but I hardly remember anything about it.
+1 for:
any ID Software game (DooM/Wolf3d/Quake/hexen/heratic)
any Sierra/Sierra On-Line game
any Duke Nukem game
C&C (any)
Descent (any)
Full Throttle (I am anxious to see FT broken)
Return to Zork (get the CD-ROM ones for better music, dunno about the other Zork games though)
Tomb Raider 1
Jazz Jackrabbit (any)
Civilization (dunno about game goals though...)
Colonization
Magic Carpet (I barely got to play this game by the time windows 98 took over my computer -_- )
Blake Stone (AoG I've played, but not the other one)
Betrayal at Krondor (never did finish it, was too young to understand RPGs)
Carmageddon (Cuz we can hehe)
Destruction Derby (I had #2, and boy the computer is out to get you in this game)
Chessmaster 2000 (I know i know, it's boring, but I would LOVE to see it pwn'd IN THE FACE)
X-Com (or UFO: Enemy Unknown), the first one. Terror From the Deep = boring imo
Math/Reading Blaster (really old game I used to play, I'd love to see it broken apart)
Mechwarrior (pretty much any of them, I'd LOVE to see MW2 and MW2 Mercs especially.)
Need for Speed 1 (cuz lord knows I was a BAD driver when I was 5)
OREGON TRAIL (PRESS SPACE BAR TO CONTINUE, riding the west of the Buffalo Menace 200 pounds at a time, dying of dysentery, FORDING the 12-foot deep river... epic times ftw, game goals imo: total party death as fast as possible / make it asap)
Sim City 2000 (there was a SNES thread about it, but goals would be a problem... maybe the scenarios or 1million pop or something)
Unreal 1 (the game my comp wasn't good enough for :( )
Warcraft (any)
ZZT (Town or any good set of levels)
Yes there's plenty of other games out there, those are just the ones I can honestly vouch for (and that I can remember clearly).
Edit:
Terminal Velocity
^D'OH How could I forget about this gem. I shoulda just said "any 3drealms game" and called it good.