EggRobo is consistently faster/more difficult to beat. I don't know about running speed, but Knuckles definitely can't jump as high as Sonic can, and that alone makes some bosses difficult. However, Sonic Team deliberately designed Knuckles' playthrough of the game to be more difficult, and a large part of that was more difficult bosses. It could be that the jump height, combined with the likelihood of accidentally gliding, makes that boss difficult enough.
Oh yeah, and one of the bosses ALWAYS shows Eggman, no matter who's playing. IIRC it's Flying Battery.