Could they even have made a jungle back in 1994?
Yes, they could have. Just apply different textures to Arena and change the tree design a bit. If we're talking about dense, impenetrable foliage, they couldn't have even done that with Oblivion and still have it run smoothly, but the fact of the matter is that in both games Cyrodiil was ever shown, both before and after Morrowind's lore stated some contrary, Cyrodiil was clearly still the cosmopolitan, deciduous forested seat of the empire. I just loaded up Arena for a minute and even decided to check out good old Vvardenfell for a bit. It certainly looks different, too.
About Sutch moving, go check Ebonheart on Arena's map.