More dangerous terrain elements.

It'd be nice to have obstacles more than mines when navigating across certain maps. For example, some could have bridges over cliffs that crumble when too much weight is applied on them.

There could also be rapids that make your vehicle get trapped in its current once in it.

Patches of grass that vanish when you step on them and leads you to a hole filled with spikes.

You get the idea.
The bridge idea is really cool, although it could easily be defeated by a flying vehicle, same with most obstacles.

It would be really cool to have underground missions, since flying vehicles in besiege are OP and can beat most levels, being underground would force the use of smaller, ground based machines, which would be cool and would add some real difficulty.

The undergound missions could take place in a cave with a hazardous crumbly ceiling, or with collapsible bridges going over lava. Maybe you could have to transport bombs to blow up the foundations of a huge castle (which was a legit tactic for destroying large medieval strongholds) or use it to blow open a heavily guarded underground vault to steal loot.

If none of this is feasible, (I'm not sure what the capability of the engine is), then maybe just add some difficulty modes, which restrict the use of certain blocks (i.e. flying blocks) or set a block limit for a given level. That would give a genuine challenge and breathe life into some of the older levels which we've all played to death :)
Ooh forgot to mention, putting a time limit on future levels would be awesome, you could have to preform a task before a timed bomb goes off, maybe rescue a peasant from a castle which is rigged to explode, or protect a village from other siege machines or enemies for say 3 minutes.
I think that having longer levels in general would be great.
The ones we have so far can be completed in seconds, having a long-@$$ level would be nice for any kind of racing or performing a test flight without the need to turn around constantly because of reaching the end of a a map.

What about multitasking? Make a puzzle level that requires you to build two separate machines in two separate bounding boxes, then operate both at the same time to pass the level - like a forever alone coop game c:

Edit: Yaaaay, 100th post