Getting his tail on fire/hitting the giant spikey ball with those green plant things/hitting the weak spot in the boulder, and having to spin attack him while he's spinning around the small world > swinging him by his tail and throwing him into bombs >>>>>>> destroying his bath tub.
64's was lots of fun when I first played it, but the Bowser fight seems almost too simple now. Doesn't help that when you start running around in circles trying to get his tail, he merely spins in a circle (ad nauseam, without the nausea). Sunshine's boss was... well, slightly disturbing.
RANDOM DISCUSSION: I always thought it was an ax. You'd think Mario would just lunge at Bowser with it and finish him once and for all. Ah well, at least there's Fire Mario.