Here’s an idea I had earlier: Arbitrary board sizes.
The minimum would be like 80×25, the screen size, and connected boards would have to have matching edges. That is, a board that’s N tiles tall can only be connected on the east and west sides by boards that are also N tiles tall.
Surface boards could be 128×128, or 128×64 to adjust for tall tiles, which would make for nice “powers of two” work and fully covers the equal side lengths rule. Dungeons could be any size, considering those are currently only connected by stairways and such.
This would of course invalidate old saves.