I think what makes truly memorable boss fights is taking normal game features and pushing them in a new, interesting way. Mario and Zelda are good (and ubiquitous) examples- every skill the player has can be used in a boss fight, and typically in ways not explored previously. So I think you're part right- Bosses should be bigger, more health, ...