As a runner/TASer of the GBA Metroids, they have a fair share of interesting boss fights:
Fusion 100% Yakuza - Does enough damage in the first phase to skip the second phase of the fight completely:
http://www.youtube.com/watch?v=8EOBTd99nnY&t=55m17s
Zero Mission Brinstar Worm - Hits with three missiles on the same frame to kill instantly. Might be hard to follow unless you know the game and/or watch it in slow motion:
http://www.youtube.com/watch?v=tBMMiw4TX6Q&t=1m40s
Zero Mission any% Ridley - High Flying antics and lots of projectiles flying around:
http://www.youtube.com/watch?v=tBMMiw4TX6Q&t=10m40s
Zero Mission any% Mother Brain - Collecting a lot of ammo mid-fight. Also uses tight precision shooting to kill her in 3 rounds as opposed to the usual 4 realtime runners do:
http://www.youtube.com/watch?v=tBMMiw4TX6Q&t=19m10s
Zero Mission 100% Imago - Nothing more than precise missile firing, allowing the boss to be killed in one round using only one super:
http://www.youtube.com/watch?v=IyCm3wVJSE4&t=20m47s
Zero Mission 100% Mecha Ridley - Just a fast kill with some fun acrobatics, might be confusing to some if they don't know that the boss's health triples when you collect 100%:
http://www.youtube.com/watch?v=IyCm3wVJSE4&t=59m50s
Zero Mission low% Kraid - Uses crazy morph hovering and bombs to stay in Kraid's face the entire fight. Also features some great drop manipulation:
http://www.youtube.com/watch?v=4TZi3OtsZb8&t=14m30s