I think it would be cool to have really really big bosses randomly appear, difficulty according to planets level. Come from the background, I mean massive bosses. They should not appear too often, but when they do and you defeat one, it should be worth it by reward.
Well... We already have mini bosses. If epic fights are what you are looking for, then a not-so-RNG dungeon with a predetermined boss and reward would probably be better. Near idea though. I like it!