I don't think an extra-galactic Empire would make much sense. Since if they covered the whole Galaxy, why don't we know about them? Unless they're Xindi...I was thinking what kind of Empire.
Member of one of the others.
An AQ or BQ player in Galactic Events
Dominion sized Empire
Extra-Galactic or Extra-universal massive Empire and a few things in between.
Maybe a Tholian or Gorn sized and another option a Klingon or Romulan size.
I think the other options you put up are a good set of choices.