This got me thinking. Here's a throwback to Star Trek history... the Kelvans. They're presumably still out there in the Andromeda galaxy, and would still need to relocate. They may not have any idea that the Federation made peace with their scouting party, and may not respect that peace, even if they did know.
By their own admission, the Kelvans are conquerors. If they were to launch a full-scale invasion of our galaxy, that would certainly qualify as a big bad. And an advanced species who can shapeshift and blend in among the various races of the Milky Way, but whose true form is a large, multi-limbed tentacle monster? Well, there's your creepy. (Imagine what they could do with that with modern effects, which would have been impossible in the TOS days.)
All you'd need is some way to get them to Federation space quickly, without a 300-year travel time. Hmm... anyone know of a mysterious portal lying around that we haven't yet learned why it exists?