Maybe what they can do is add a "secret" or random boss to dungeons, similar to how bonus wanted mobs spawn in leves. Maybe add a puzzle to get to the boss if it does spawn too.

I think the biggest challenge is how to make bosses with unique mechanics that seem fun but not gimmicky.