I messed around with the Settlers IV demo and I may have come up with a solution. If you'd test it out for me with the full game I'd appreciate it.
To add widescreen support to this game you'll need a hex editor such as Be.HexEditor. Open your gfxengine.dll file (located in the Settlers IVExe directory) with the editor and search for the following string:
00 05 00 00 bb 00 04 00 00
00 04 and 00 03 represent the resolution 1024x768. Change it to whatever resolution you need.
1024x600 - Replace 00 04 with 00 04 and replace 00 03 with 58 02
1280x720 - Replace 00 04 with 00 05 and replace 00 03 with D0 02
1280x800 - Replace 00 04 with 00 05 and replace 00 03 with 20 03
1366x768 - Replace 00 04 with 56 05 and replace 00 03 with 00 03
1440x900 - Replace 00 04 with A0 05 and replace 00 03 with 84 03
1680x1050 - Replace 00 04 with 90 06 and replace 00 03 with 1A 04
1920x1080 - Replace 00 04 with 80 07 and replace 00 03 with 38 04
1920x1200 - Replace 00 04 with 80 07 and replace 00 03 with B0 04
Save the file and change your in-game resolution to 1024x768.
I've tested it in 1280x720 and 1280x768 and it seemed to work fine. It's pixel based, so the higher the resolution, the more game area is rendered.
Unfortunately the HUD also seems to be pixel based, so the smaller the vertical resolution, the less of the HUD you'll see. The HUD is designed around 1024x768, with 800x600 having one section cut off, and 1280x1024 having an empty section tacked on. So as long as your vertical resolution is 768 or higher, you should see it all. If your vertical resolution is higher than 1024, though, it may do something funky with it, so let me know. If it's between 600 and 768 (like 1280x720 for example) it cuts off part of the bottom section.
1024x768 (4:3)
1280x768 (16:10)
I'll look at the Settlers 3 demo later. I had a copy of Caesar II but I can't seem to find it. I sure hope I didn't toss it out.
[Edit]
I tested it in 1440x900 and it works as well, though that computer is newer and the message boxes are sometimes black (but that happens with the normal resolutions as well so it's probably not an issue with the fix).