My group feels that Pandemic is easier with fewer players, so as player count goes down we increase the epidemic count to maintain the challenge level.
Other adjustments will depend on how you think the difficulty changes. In player counts that you consider harder, try dealing out multiple roles and letting players choose, or try choosing play order only after seeing roles and starting cards. For player counts that you consider easier, reverse these decisions.
On the Brink adds some variability and complexity. I'm not sure if (after you get past the learning curve of any new variant) it adds difficulty, but it might.
