1) квест (вполне подойдет для ПРЕДпоследней миссии людей)
убить духа Огня (Льда)
если убиваешь, лучникам (например) даются стрелы огненные (ледяные)
2) классическая охота на героев
в какой-нибудь миссии где у противника в совокупности штук 5 героев, можно устроить охоту на героев...
награда - книги и артефакты
3) как я уже предлагал - чтобы начать постройку кораблей (или чего-то другого) надо собрать определенное количество ресурсов
4) а-ля дьябло 2... на базе есть портал неработающий, если найти 2-ой (который стоит в очень укромном месте, и в очень полезном) можно будет его использовать
5) для орков - тролли, для людей - дренеи
спасаешь вождя племени из лап противоположной стороны и тебе даются см. кто
6) Неугодный полководец
например некий мастер клинка отказался подчияться демонам. если помочь ему, он в кам присоединяется.
7) поиск древнего и великого артефакта...
8) в миссиях где просто бегаешь войсками можно добавить поиск кладов
9) самое сложное, самое долгое и самое крутое - нелинейность сюжета... хотя бы в несколких местах. выбираем 3 ключевые главы и от них делаем разветвления
10) подлая война
убиваем-с вождя и противник начинает играть хуже.
ну что, у меня думалка в том направлении работает?

Varimat добавил:
пока свежа мысль, за ночь могу забыть...
подойдет для морской миссии
некий могущественный существ устраивает штормы на море и топит корабли людей (аура волшебников в даларане)
надо его убить чтобы можно было нормально вести бои с ордой
в даларане аура настроена на тип "нежить"
можно малоиспольуеый тип "келикан" переименовать в "корабль" и дать кораблям людей
сам дух - орк шаман или дух вды или нечно такое, в союзе с Ордой (этим объясняется незатопление флота орков) будет сидеть на каком-нибудь небольшом острове