Heroes IV differs from all others in the fact that you can have a party of JUST heroes(and these are actually the most efficient by a significant margin, but can only really occur in long campaigns where you have the chance to level multiple heroes to 20+), or an army of just creatures roaming the map. Terrain plays more of a part in battles, and there are potions(something that doesn't exist in other HoMM games) that can give your heroes(can't recall if they affect units, It's been a while since I last played) various special effects, such as raising up after dying back to full health, restoring their health, increasing their resistance to various types of damage, giving them haste, etc. Most of these can even be applied on the overworld map, so if you think you're about to enter into a rough combat you can pre-apply a bunch of potions without having to waste time in the actual battle.
As has also been mentioned, combat is not side to side, but at a top down diagonal view, which is what I think increases the terrain navigational difficulties. The leveling system is significantly different from I-III, and is the basis for V and on(though IV is still significantly different in this area), you basically pick the skills you want your hero to have(which affect both your heroes and your creatures performance) and depending upon the skills you pick, your class itself changes, giving you specific extra bonuses to what the game thinks your doing(If you go with 3 or more types of magic mastery, you become an archmage and gain a 20% damage boost to all spells).
Another different thing is roaming creatures. In other HoMM games, guardians of treasure or mines are static, they don't budge. In IV they will wander around the area they are guarding, giving you a chance to sneak in and grab the treasure without having to fight them if you think they are to strong for you. They also have aggro ranges, so if you get within a specific distance of them and remain within that distance when your turn ends, they'll come after you. One of the classes, the Thief, has the stealth ability which improves as you level, giving you the ability to just walk right up beside anything, take the treasure, end your turn next to the monster, and still not get aggro, which is pretty cool. Another class has the ability to sway creatures from any neutral stack to join your cause, but even creatures from opposing armies if you significantly overwhelm them in terms of power.
Another significant change is caravans. In I-III if you want to recruit monsters from dwellings outside the castle, you have to manually visit them and recruit. IV is the first game to change this by introducing caravans, which allow you to recruit from those dwellings and have them make their way to your castle, though opposing armies can ambush them on the way, as can neutral stacks of monsters if they end up within their aggro range. IV actually takes this a step further then V-VII in the fact that you can caravan troops from one castle to another as well, including heroes. Now, this may not sound that useful, but it is actually quite a time saver if you don't feel like manually bringing a hero from one castle to another ^^.
The final change is creature recruitment itself. In other HoMM games there are 6 to 7 creatures that can be recruited in a castle, and you can upgrade each of those creatures to a 2nd(and sometimes even 3rd), superior form. In IV you can only have a total of 5 creatures in your army: Both Tier 1 creatures of the castle, and then after that(and this is something I both liked and disliked) you have to choose between which Tier 2, 3 & 4 creature you want to recruit. It adds a significant amount of strategy to the game and how you want to play it, due to you having to choose usually between something with ranged, or a melee creature, or for example, the necropolis has you choosing between the Devil which can summon Ice Demons to your cause in battle, or Bone Dragons who have the ability to cause fear in the target they hit, causing them to flee.
Edit: ProTip: Take over nature castles as soon as you can when playing against the computer. The AI prevents them from utilizing it's special feature, which is an additional creature recruitment center. I've snagged nature castle midway through a map and found dozens of level 4 creatures(fairy dragons) or 100+ level 3 creatures(waspworts, ranged with special effect of lowering enemies attack) just sitting in the creature portal(that's the actual name of the building iirc. It basically gives you the option of recruiting dozens of special tier 1 creatures, a dozen tier 2, a couple tier 3, or 1 tier 4 a week).
Ooooohh, that reminds me, creatures don't come in once every week like all other HoMM games, they come in gradually throughout the week depending upon how many the creature dwelling can generate in a week. It's again both good and bad. Good because you're never entirely defenseless if you lose your primary hero, bad because you can't get your entire weeks worth in one go at the start of the week.