NeoZeedeater named a lot of cool games that I missed, though I was trying to restrict myself to games that are either exclusive to or clearly superior on C64 and Amiga. I must disagree on the Last Ninja games. I thought they were horrible uncontrollable messes only partially redeemed by the excellent graphics and music.
Impossible Mission is a great game, though I'd be surprised if you haven't played a version of it by now. It's apparently coming to Wii VC.
Cybernoid 1 and 2 are nearly impossible, but they're still fun. Some of the best music on C64 as well - Jeroen Tel is awesome. The ports sucked, but be sure to listen to his arrangements of Afterburner and Outrun.
Ghetto Blaster is an interesting game. It takes a while to understand how the street layouts work and the actual goals of the game, but it's fun once you get the hang of it. Groovy music, too.
Monty On The Run is a typical stupidly hard nonscrolling platformer. With the best music on C64.
Centauri Alliance is a first-person party-based sci-fi RPG. It's a lot of fun, and includes the strange ability to import characters from Ultima and Wizardry games. The combat system is a hex-based affair vastly unlike many other RPGs of the day.
Mercenary is a really deep and complex nonlinear first-person adventure game that uses the same vector style as Elite. There are two sequels on Amiga, using filled polygons instead of vectors but retaining similar gameplay: Damocles and Mercenary III: The Dion Crisis. Damocles was apparently going to be ported to PC with even better graphics, but Novagen went out of business before it could be completed.
Le Mans is a simple Monaco GP clone made by HAL... the same HAL that later created Kirby. There are a lot of similar games on other systems, but I can't think of a better blob-dodger on C64. It supports the 2600 paddles for analog control.
I don't like Spectrum. I think the graphics and sound are an absolute mess, and the gameplay suffers because of the limitations of the machine. That said, there are two Spectrum games that I love: Lords of Midnight and Doomdark's Revenge. They're complex strategy/RPGs that are absolutely huge. They came out on C64 as well, so I thankfully don't have to use a fucking Spectrum or emulator to play them. PC versions were also included with the third (and PC-only) Lords of Midnight game - the only redeeming feature of that mess.

