I'd say that during my first playthrough of Cave Story the hardest boss to me was probably the undead core. Not because the fight against it was very difficult (actually quite easy, what with misery providing you with rockets and health galore) but everytime i came there since i wasn't good enough to fight the preceding 3 bosses without losing to much health i was always 2-3 hits away from death and sue almost always got me, plus i was using the machine gun, which isn't nearly as potent against the core/doctor/misery as the Spur (Im currently in the midst of trying to get through the sanctuary, so i haven't gotten past ballos' first form yet :/).
Edit- Granted, now that I can get past the misery and doctors first form battles taking relatively little damage its quite the pushover, kind of a tough one on what my hardest would be now, although the first form of ballos kicked my butt in the first 15 seconds of the fight, yknow what, scratch that, that robot you fight (forgot what its called) right before the ballos fight is the hardest >.<