(Please comment and give thoughts)
Though Heroes V has caught up with the majority of the factions that were lost since Heroes 3(Stronghold in "Tribes of the East" and the Return of the Dwarves in "Hammers of Fate"), they are still yet to reintroduce my favorite faction from the game, Fortress. Fortress brought a unique aspect to the game that was neither seen before nor after Heroes 3 and it is something i would wish to see again.
It could be even be taken a step further with the introduction of a Sea faction. In no game that i have ever heard of have i seen a playable Sea faction. I believe it would open the doors to a very unique and enjoyable expansion. There is so much myth and legend behind the Sea that can be exploited. Like the Leviathan or Kraken and so much more. The sea itself, even without myths, is a beautiful and mysterious place. I hope you agree with my thoughts of incorporating something the no game has seen since Heroes 3.