Osman/Cannon Dancer has some awesome ones.
Demon's Crest first boss is quite a shock.
First boss in Strider is a total pushover, but goddamn.
Warrior Blade: Rastan Saga III has some awesome bosses (beat 'em ups usually don't). They are unusually not-cheap for beat 'em up bosses too, if a little easy.
Final Boss of Midnight Wanderers is god, so that's something (I know you fight god a lot in games but hey)
Stage 2 boss of Run Saber is awesome/creepy: http://www.youtube.com/watch?v=TwzWcPf3L8c
Final boss of Atomic Runner for Megadrive is pretty epic - it takes place on the top of Lady Liberty: http://www.youtube.com/watch?v=DaDGiYcgoaY
Boogie Wings has very epic booses, especially the xmas level.
Pretty much every boss in Darius Gaiden is epic.
Last boss of Narc is a giant skull that vomits tongues at you, that flop around like fish on land.
Black Heart's first boss is pretty nutty.
Giant underwater multi-faced titan from In the Hunt is a good one.