So what changed
The most obvious change was in regards to movement across the maps. In D:SL and DII parties could travel anywhere on the map restricted only by mountains, this included the ability to travel over water (with the water bound party being represented by a boat) at a significant move penalty. In Renaissance / Resurrection this was not the case, movement was heavily restricted, parties were only allowed to travel along designated paths and at no point could they move across water. In Reincarnation this is completely reverted, parties are no longer restricted to a path and they can once again move across water. This change alone is a prime example of why these changes could not be simply pushed out as a patch because it fundamentally changes the flow and strategy of the game, and as such the maps were updated to accommodate these changes.
Something I forgot to mention regarding travel over water in D:SL and II is that various party leaders came with the ability "flying" which allowed them to negate movement penalties from moving over various terrains which allowed them to travel over water much faster than other units. The drawback of this was that they did not gain benefits of moving across advantageous terrain such as paths. The return to this travel format in Reincarnation has resulted in:
No flying heroes. Makes sense, since the heroes weren't changed from Ren/Res, and you can only embark on water at specific points. - (Azaghal)
The next change was in regards to combat. Anyone who has played D:SL or II knows that combat took place on a static 2x3 grid meaning parties were restricted to 6 units, 5 normal + 1 party leader. In Ren / Res, combat was changed to a hex grid system allowing for much greater freedom and tactical gameplay. Whether or not you liked it was a personal preference, but simply put it was just a different way of doing things. To accommodate the new combat set up various other things were changed, ranging from unit statistics, party sizes and character progression. The numerical values in Ren / Res were extremely inflated compared to older games, health values for example ranged into several thousand where in previous games they rarely surpassed a few hundred and that was only for very highly leveled units. The addition of combat runes, and a larger party size of 8 (7 normal units + 1 leader) means it's understandable why these values were chosen but the impact it had on the games was profound, often times making battles drag out longer than they really needed to. In Reincarnation various changes were made to combat to address this. Unit stats are toned down to modest values and the size of the combat arenas have been reduced meaning that combat now sits as a kind of middle ground between the old 2x6 static grid and the large hex arenas.
To fit with this party size has also been reduced, the maximum leadership nodes have been reduced to 2, meaning a party can have 5 (normal) + 1 (leader). A new mechanic has been added that allows a leader to hold units "in reserve", up to a maximum of 4, units that do not engage in combat but can be swapped out anywhere on the map
Character progression took a drastic change in moving from II to III, normal units evolved much the same, purchasing upgrade buildings at your capital allowed them to transform into an improved unit once they had gained enough experience. Party leaders however gained the stat distribution (5 points per level) and a final fantasy 12 style talent grid (2 points per level) that gave them access to addition stat boosts, addition skills or the coveted leadership abilities to increase party size. What changed in Reincarnation is that every unit now has a similar system, so that means every normal unit now has their own simplistic skill grid as well as stat distribution. They are still restricted by the old rules governing their evolution but the added flexibility in how you want to use these units can make a big difference, especially considering the more modest values. The various tiles that appear on these grids also have been updated, as mentioned before, leadership has been reduced, but other tiles such as "Reserve" have been added.
One thing I wasn't aware of so thanks for the replies: units now need to gain three levels before evolving. They gain levels faster, in return. What this means is that units don't receive as huge a spike in powers when evolving, but gain power more gradually -(Azaghal)
A very important feature that was removed from D:SL and II was the usefulness of thieves. These units were integral to the game due to their unique abilities such as stealing items from enemy parties or stores, poisoning enemy parties without engaging in combat, or to the guild leader "hero type", inciting riots in towns or stealing spells etc. In Ren / Res all of these abilities were removed rendering the thief as just another party leader, except it required you to build a capital upgrade before you could purchase them, in short, they were a complete waste of gold and stone. With the changes made to the talent grids in Reincarnation the thief takes a small step back to his former self, regaining the ability to poison parties on the overmap and the ability to steal items from enemy parties.
Other things that have changed, the overworld spells / runes have been adjusted to have more modest values, plus they appear to be much more in line with previous installments "thematically". The spells in Ren / Res were rather homogeneous across the various races, not identical but not amazingly diverse.
"Energy" is now also required to use runes in combat, a system that was not present in any previous game. (I can not comment on the addition or changes made to the runes specifically since I have not checked at the time of writing this).
Energy limits the use of potions too , not just runes. The implication is that potions are much weaker for combat purposes. For instance, you usually won't have enough energy to use more than one revive potion per battle -(Azaghal)
Veteran heroes can be rehired for free from the start. You no longer have to wait until you have enough gold to recruit him/her, by which point that hero is underleveled and useless. This actually means that you can "main" a hired hero and let the unique hero tag along. -(Azaghal)
Moved from the unsure section where I had mentioned that ruins in D:SL and II were a hire risk, high reward encounter providing good items or resources upon victory. These were changed in Ren / Res to a low risk, low reward, repeatable every 10 turns affair severely limiting their overall worth.
Ruins are a mix of the D2 and Ren/Res system. Most are easy and repeatable with crappy rewards, but some are very hard and drop unique loot on first victory. Still, as noted above, you can peek at units in a ruin before engaging, which removes the risk/reward flavor from them - (Azaghal)
Other misc changes include a few new enemies, changes to items/ new items etc.
New voice actors for the intros, noteworthy because I know some people hated the old voice actors.
What has not changed.
The story. As I mentioned I haven't played the game extensively yet so it's possible that a few side quests have been updated / removed / added but for the most part the main over arching story is the same as Renaissance / Resurrection. To that end you are still expected to use the faction hero (Lambert etc) throughout the campaigns.
Player controlled units. Aside from stat values it appears that most (all?) upgrade trees are untouched. Aside from potential mercenary camps there's no new units to order around.
edit: Initiative functions as it did in Disciples III: Resurrection. For those unaware, the changes made to initiative between Renaissance and Resurrection were pretty unforgiving. In all games up to Renaissance initiative was pretty simple, units attacking in order from highest to lowest. In Resurrection, after every units turn the value of the lowest initiative unit alive in combat was subtracted from their initiative allowing high initiative units to potentially get multiple hits in per turn. It was pretty unintuitive and incredibly harsh, especially on base undead units since they are typically very slow. Once you understood the mechanic it wasn't so bad.
. ToME is always a 
