If any programmer would like some motivation, let me describe some games I have in mind.
Beach Head II
This is actually four two-player games in one (The CPU can play as either of the players). Game A (my favourite) has one player control an army of soldiers who need to run back and forth between cover in order to avoid getting killed by a gigantic machinegun turret. The first half of the game, the first player is on the defensive while the second player tries to pick off as many soldiers as possible and get an early score advantage. The second half, the soldiers can simply run for it, or go on the offensive as they get close enough to hurl grenades at the turret.
A TAS of this game could be played many different ways. As the second player, the author could try to kill all the soldiers as soon as possible. As the first player, the author could do numerous things.
A. A timeattack where he tries to get the survivors to the end of the level as quickly as possible, sacrificing soldiers in order to save time and still end up with a higher score.
B. A no-deaths run, where every single soldier survives. (Conventionally impossible)
C. A maximum score run, where you blow up the turret as many times as possible. (Probably not as fun to watch since the game is halted every time the turret is replaced)
Commando
A simple bird's eye shooter where you shoot down soldiers and throw grenades in order to get through three short levels. The game's a little easy, but I think a speedrun would be fun to watch if the player does something impressive like use no grenades, or only grenades, or kill every single enemy.
Forbidden Forest
You play a hunter who must venture through a forest armed with only a bow and arrow and fight a variety of monsters such as giant spiders, dragons, big leaping frogs, ghosts, and skeletons. Incredibly violent (if a frog lands on you, you splatter. If a spider touches you, it sucks your blood out) and also kind of scary. Especially the last boss who you can't even see, except for a silhouette which is hard to see, since the sky is pitch black by the time you fight him. He moves around as well. The only times you ever really see him is when lightning strikes and after this happens five or six times you can clearly see that he's getting closer. If he reaches you, you lose all your lives and get a game over.
A TAS of this game might be interesting, as part of the time consuming nature of the game is that it's hard to line up a good clean shot with your bow and you often have to make a run for it, reload and then come back to fire the next shot.
Fort Apocalypse
You fly a helicopter to rescue captives, destroy tanks, avoid airborne mines and then fly underground through a deep underground labyrinth, until you reach a strange fortress, blow up a reactor, and then escape. The need to occasionally refuel and teleporters add some fun elements to this odd game.
Green Beret
A side-scrolling game where you play a soldier armed only with a knife that must take on entire armies. The enemy troops are armed with guns, and so much as touching them kills you. A fun but extremely tough game. Flamethrowers can be found in the levels but only give you three shots.
International Karate
Unlike most fighting games, this one's fairly unique in that it defeats the purpose of button-mashing. All attacks do the same "damage" (every successful hit is a KO) meaning there's no uber-attacks that make the others less than useful. All attacks are equally useful, but are to be used in different situations. Example, a stomach punch is better when you're up close, but a jump kick is better when you're further away. If the opponent is blocking low, you do a high attack. If they're blocking high, do a leg sweep. Since you can mix it up and use just about any attack, watching a TAS of this game wouldn't be as boring as say, a Street Fighter 2 TAS where someone might do the same move over and over again.
International Karate+
Same as above, but with different moves such as backward attacks, backflips, and headbutts. Also, you face two opponents at once, meaning the fights would be more intense.
Jumpman
Mostly a very simple game, it can get slightly more complicated in later levels. You control a character who must jump to avoid obstacles and enemies which vary in creative ways, in order to collect all the treasures in each level. Some levels have a puzzle aspect to them. Some occasional levels have particularly unique twists, like "invasion" where you forego your jumping ability in favour of a gun with which you can shoot down UFOs, or "Dragon Slayer" where instead of jumping you hurl spears. Another is "Hot Foot" where every time you jump the ground beneath you is destroyed (meaning you have to be careful where you land)
What would make this particularly fun for a TAS is that you can choose a speed from 1 to 8 (1 being fastest) to play through the levels. Everything in the level, from your jumps to the timer is faster if you pick one of the faster speeds. Speed 4 is default, Speed 2 is much more challenging. Speed 1 is insane.
Lode Runner
This game was released for NES too, but I prefer the C64 version since it's a little faster paced and it shows the entire board (In the NES version you were shown a closeup of a cross-section, meaning that it was harder to see what was going on elsewhere in the map. This maybe makes it a bit more challenging to record, but it also means the viewer of the TAS has a harder time following along)
For those unfamiliar with the game, you climb ladders in order to collect treasures while avoiding enemies. The unique part of the game is your ability to create holes in the ground, in order to trap enemies or give yourself a quick escape if you need one. Different levels are designed for you to use this ability in a variety of ways. Example: At least one level requires you to trap an enemy and have the hole reseal itself while he's still inside so that he's killed and regenerated over a treasure that he picks up, so you can take it from him.
Space Taxi
A really nuts game where you control a flying taxi that must pick up passengers on all sorts of weird planets and alternate dimensions and take them to their destinations, despite really really crazy obstacles. The physics are what makes this game challenging, especially on levels where the physics are manipulated by things such as black holes. Some luck manipulation would work wonders on this game, such as getting passengers to appear at the closest possible landings, and getting them to request the closest possible landings.