In 3D games? Gosh... I guess Demise from SS was a bit of a pain until you learn how he works, but none of them were all that challenging to me.
If you open it up to 2D games, definitely either Thunderbird or Iron Knuckle from AoL. Then again, I hate any Darknut or Iron Knuckle from the first two games.