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.
Best Answer
If you are willing to start replacing rule subsystems to improve the drama, then you could take a leaf from the FATE Fractal (see more) and model suffering from the disease with a skill challenge.
Model as Skill Challenge
Since the default rules for skill challenges aren't as good as they could be, try these alternative rules. Diseases should be a complexity 1 challenge under this system.
During play, the skills used would represent the various actions the group takes to deal with the disease (whether it has infected one party member or multiple members). This could range from hunting special herbs with Nature to using Diplomacy to persuade an innkeeper to use a room as a sickroom.
Each failure in the skill challenge would move the infected one step closer to the final state. If the skill challenge fails as a whole - the infected suffers the final state and the disease fades over time. If the skill challenge succeeds, the infected suffers the worst state they reached for a short time and the disease disappears quickly.
Each disease should be different. Creating skill challenges allows you to go into more detail about the struggle with disease and make it more interesting than a few Endurance rolls.