As someone who has recently designed built an adder, just throwing in my $.02:
As far as mechanical logic goes, the most useful thing I can see being implemented is a rotation sensor, which would easily reduce the complexity, power requirements, mechanism requirements, size etc. of my adder by half or more, though I hear that point is a dead horse by now. They would need a delay, or it would be trivial to make a device that is both powered and unpowered. Overall I think this is a bad idea because it makes complex logic ridiculously easy and not at all entertaining.
Beyond that, XOR AND and OR are easily implemented with 1, 2 and 3 gear assemblies (respectively), so coding those as specialized gear assemblies/machines would be a complete waste of time.
A NOT would be useful logically, but mechanically it wouldn't make sense, only transferring power when unpowered, though if a rotation sensor was implemented it would be trivial to hack one together (especially if it worked like a pressure plate, with a settable threshold of 'ON ABOVE/BELOW').
One thing I discovered while building the adder is how much of a pain in the ass it is to build a complex machine without the ability to select a part by the cursor. Selecting from 200 identical Siltstone Gear Assemblies is a pain in the ass, particularly when the lever is on a different floor and I need to make an educated guess at which bit of the adder I'm making. Also helpful would be the ability to unlink levers or at least show linking connections.
Also having a (smaller, maybe 1-2 frame) delay between an axle turning on and a mechanism moving would be neat, just as a tweak.
Fire would be an awesome addition to the fortress, being able to light my own would be excellent, a logical extension is using the light from a fire to illuminate parts of your fortress (which would be a complete pain from a logistical standpoint, and thus needs to be implemented SOON).
A conveyor belt would be nice, though anything like a door that moves an object occupying the space when 'on' would be sufficient for me to build my own.