I think that the terrain makes the boss encounter fun or not, at least with AVWW. Skelebots in particular are usually fairly boring encounters because a) their tallness means they get stuck often and b) their attacks are too slow and boring. I'll use Balrog as a comparison point as he's a good example of a fun boss fight in his various incarnations: The rooms in which he is fought tend to be small and basic--I belive that you mentioned smaller Boss rooms in the OP. Good stuff. However, he also moves quickly and dynamically--in contrast to Valley's bosses (except for Amobeas) which move pretty slowly back and forth across the ground. In CS boss fights wherein the boss has a ranged weapon (Labrynth Balrog, Ballos, Misery, The Doctor, The Core, Omega, etc.) it fires quickly and usually with a great many projectiles at once. This rewards skillful maneuvering and makes the combat overall more intersting, which is why I think that the Amobeas are Valley's best bosses since they have these elements. LaughingThesaurus also has a point that a greater variety of attacks makes a more interesting fight. Plus the multi-stage nature of most bosses which gain more attacks as you do more damage. This was also mentioned in the OP which is a good thing.
Let's return to the rooms themselves: A lot of AVWW Boss rooms are quite large and intricate, which leads to wasted space. Cave Story Boss rooms are only as large as they need to be--Most rooms are small and the only large ones are made to fit equally large Bosses (e.g Ballos or The Core.) Additionally, any given room could potentially hold any boss, of which AVWW has quite a few, so a lot of times certain bosses suffered greatly in some rooms. For instance, my "Eye of the Storm" map was great for amoebas since it had a lot of interesting use of Airspace, but the Skelebots were less interesting since they could only use the bottom layer.
The random element is very nice, since it adds variety, but as I said it does make it very difficult to balance a large variety of enemies. I'll use Terraria as the example for this point, as it's randomly generated nature is more akin to AVWW: In Terraria, the Bosses ignore terrain. They can freely pass through ground and walls, focusing on the player. This means that any boss will work just as well in any terrain, plus it adds a lot more angles of attack to keep the player on their toes. Coupled with the previously mentioned faster speed and multiple attacks/stages provides an exciting boss fight.
One more point: In Cave Story, a lot of bosses do not do contact harm (e.g Balrog, Ballos, Monster X) except for slam attacks and so on. With larger bosses like Skelebots this helps, as it allows the player more freedom to maneuver and even take advantage of it (there is a particularly effective strategy for taking down Balrog by landing on top of him and spamming Fireball). With smaller bosses this isn't a problem, but it might help out with larger bosses.
In summary:
-Faster Speed makes things more interesting
-Greater variety of attacks, plus more shots per salvo rewards maneuvering skill
-Bosses can be made or broken by the terrain, so it might be worth considering having larger bosses be able to pass through walls and such (this also prevents larger bosses becoming stuck, as well as making any boss work just as well in any map)
-Larger Enemies not doing contact damage can add some interesting elements (already in AVWW with Urban Crawlers, of course it would depend on the enemy. Some would make sense to have a melee attack)
These are of course just my opinions.
