Think about the real world
There are many conflicts in the real world, for many reasons. Look at news or a history book if you need inspiration. Not all of them are combat encounters, many might be detective work and exploration.
- Which church is allowed to tax/get the tenth in a village? Help the priests of Pelor against an attack by Asmodeus' children (insert $LOCAL_DEITY).
- Are there racial tensions between the races? Calm the mob of elves wanting to burn all halflings.
- Who illegally hunted a deer in the baron's forest? Free the arrested farmer or help prove his innocence so he won't be executed for his crime.
- A landslide destroyed the crop in the neighboring village, and they are running out of food. But giving them food from this village might lead to starvation in winter.
- A Party member is unfairly accused of theft. The punishment is cutting off the left hand. Fight the guards? Escape the guards (Skill challenge?) Prove innocence (How?)?
But much more important than the exact back story is in my eyes:
Make combat encounters diverse
It's not (only) the creature selection that makes an encounter interesting, but how you set up the battle. Let me make an example, with the same old 'bandit take village hostage' in three variations. I'm sure if you run it like that, the players won't complain it's always the same.
Devious, planning ba...ndits
The bandits have obviously heard of the wandering band of do-gooders and are prepared. First, they send in the dogs. Use skirmisher dogs that charge + make the enemy prone. Feel free to give them half HP or make some of them minions in order to make the battle shorter, but use enough different dogs they can't be locked down.
The dogs are backed by ranged attackers on the roofs behind chimneys - that means ranged attacks from cover, plus potentially combat advantage if they hid well. To get on the roofs, require at least a move action + athletics check. You can also make them minions, or at least some.
After two rounds, when the party is likely to be softened up, send in the Hog-Brothers, two large, burly fighters, brutes that will focus on the same target to make it go unconscious...
Trees are fun
Bandits have taken over the village, but the village is on a hill. When the party approaches, the bandits roll logs (trees) down the hills. That's a nice trap against Reflex that damages, secondary attack against Fortitude that slows. Once the party is up the hill, use charging brutes that push them down again. As always, use cleverly distributed archer minions to make it more dangerous.
Hostages
Again, bandits take over the village. Everyone is on the village square. When the party arrives, two bandits in the center threaten the peasants that were rounded up. Can the party lock down the two bandits and prevent an all-out slaughter, while fending off the other bandits? If you make the villagers run around frightened on the battlefield, you have another nice restriction: non-friendly area attacks kill peasants.
Build up a villain/villains
Don't worry too much about 'same backstory' for side encounters, it doesn't really matter as long as the fights are interesting. And you could build up a gang of bandits that terrorize the area... every session there's another gang-related side encounter. With time, the bandits also start hunting the party. This could tie diverse and interesting encounters together. Build one or two lieutenant for every side fight that has special capabilities (not magic, but either some leaderish/controllerish powers or a especially hard brute/soldier.
I've played in and run evil campaigns of various sorts in both 3.5 and 4e (though not 5e, I think my learning will transfer), and run into a lot of problems: My Guy Syndrome comes up a lot, as does a tendency to default to a regular D&D storyline only with more stealing of spoons and kicking of puppies to remind ourselves we're evil. Sometimes an evil campaign instead descends into over-the-top motiveless violence until there's no story at all. There's a whole host of at-the-table and in-the-story issues, and I tried many different strategies to address them. Eventually I came up with a framing device which works well for us in avoiding these problems:
Provide the PCs with a Master to guide them toward orchestrated works of Evil.
Start the game with the PCs as underlings/minions/hirelings/apprentices/etc of a powerful evil NPC. The Master has a complicated Evil Plan and he tasks his minions to enact various parts as the Plan progresses: "Bring me the soul of a hound archon," "Raze the border keep," "Steal the Apocalypse Gem," "Help a spy infiltrate the paladin's ranks," and so forth, tailored to the PCs' abilities.
This provides the party a reason to work together despite having different agendas (and working together will hopefully bond them as friends so that they want to continue as a group) and establishes small achievable evil goals that accumulate into an Epic Evil Event.
All you need to do is ask the players to make sure their characters have a good reason to work for the Master: The serial killer likes having his rampages subsidised (and the Master protects him from the Law); the necromancer seeks to learn from the Master's experience and gain access to his libraries of forbidden lore; the mercenary's in it for the money and benefits.
Eventually the Apprentices will surpass their Master.
Expect the party to betray their Master at some point, hijacking his Evil Plot for their own gain: this is not only expected, but awesome. It's the Master's Evil Plot, not yours, and the story isn't about the Master--it's about his apprentices. Consider the Master to be training wheels for evil, setting an example which the party can then follow to surpass and overthrow their instructor as they level up.
This works because Evil Needs Goals.
As Ed describes so well and AgentPaper elaborates in the D&D context, evil needs concrete reasons motivating its actions. The Master provides goals and motives while the players find their feet in the new paradigm, channeling and guiding their exploration of what it means to be evil in ways compatible with the D&D paradigm without simply kicking puppies during a dungeoncrawl.
A word of warning: Alignment is tricky.
D&D has a history of the details and nature of alignment sparking major heartfelt arguments, because D&D alignments are not easily (or appropriately) matched to real-world philosophies and moralities; they're narrative simplifications to support the game's conceits and draw their power from storytelling conventions rather than from genuine moral complexity. Exactly what this means and how to deal with it are beyond the scope of this answer (and possibly this site, although there's a LOT of questions on the topic you can look at), but you should be aware it exists and be ready to talk with your players about what "Evil campaign" means to them so there aren't nasty surprises mid-game.
Best Answer
Write places apart from their location
You can make your dungeons apart from their locale. Perhaps you've written up an encounter in the catacombs of the sun god, but the party keeps walking around in the harbor district instead of the city center? Move it to the temple of the sea god! Thieves' Guild up to no good? Party has found another of their hiding spots in the rich part of town! Party finds an evil cult hiding in an old granary? Make them hide in a new granary, that burned down under suspicious circumstances!
In short, write so that the locale cannot be found in just one spot. Same goes for random encounters: they do not have to be bound to one sport. Fire, brawl fights or sudden Purple Worm attacks do not give a hoot about where in the city they are.
And don't forget: write up the crude lines for all districts of your city, from the rich parts to the poor parts to the merchant district to the market district to the harbor district and everything else.
Making my way downtown...
Make there interesting places for the PCs to see: maybe they find statues of heroes of the days of yore, or religious buildings, or cementaries, or maybe just a tavern with a funny sign outside. Keep repeating these locales as the party walks by them, so they start recognising the places. And if they start to recognise them, they start to care, meaning they will do stuff to defend these places, allowing for you to guide the story a bit more.