Minimum Tree-width of circuit for MAJORITY
Answering half of Samir's question. 

Let $G=(V,E)$ be a DAG and $V_1,V_2\subseteq V$ be two subsets of vertices of $G$. We denote by $E(V_1,V_2)$ the set of all edges in $G$ with one endpoint in $V_1$ and other endpoint in $V_2$. If $\omega = (v_1,...,v_n)$ is a total ordering of the vertices of $G$ then we let 
$$\mathbf{ow}(G,\omega) = 
\max_{i}\; |E(\{v_1,...,v_i\},\{v_{i+1},...,v_n\}|$$
denote the width of $\omega$. The online width of $G$ is defined as 
$$\mathbf{ow}(G) = \min_{\omega}\; \mathbf{ow}(G,\omega),$$ 
where the minimum is taken over all topological orderings of the vertices of $G$. Note that the traditional notion of cutwidth of $G$, $\mathbf{cw}(G)$ is defined analogously, except that the minimum is taken over all possible orderings of $G$, irrespectively of whether the ordering is topological or not.
We have the following sequence of inequalities:
$$\mathbf{tw}(G) \leq \mathbf{pw}(G) \leq \mathbf{cw}(G)\leq \mathbf{ow}(G),$$ where $\mathbf{pw}(G)$ and $\mathbf{tw}(G)$ are respectively the pathwidth and the treewidth of $G$. 

We claim that MAJORITY of $n$ bits can be computed in online-width $O(\log n)$, and therefore in treewidth $O(\log n)$. The circuit simulates an online algorithm that reads one input bit $b$ at a time and adds $b$ to a counter with $O(\log n)$ bits if and only if $b=1$. At the beggining, the counter is initialized to $0$. At the end the circuit accepts if and only if the value of the counter is greater than n/2. It is easy to see that the gates of a circuit ADD that adds one to the counter register can be topologically-ordered in such a way that it has constant online width, since this circuits just need to implement an carry on operation. The total circuit is a sequence of circuits $C=(ADD_1,ADD_2,...,ADD_n,COMP)$  where the output of $ADD_i$ is plugged to the input of $ADD_{i+1}$, and the output of $ADD_n$ is plugged to the input of COMP. Now if we topologically-order the total circuit $C$ in such a way that all gates of $ADD_i$ appear before the gates of $ADD_{i+1}$ and all gates of $ADD_n$ appear before the gates of COMP, then this topological order has online width $O(\log n)$. This construction is illustrated in Figure 1 of a paper of mine to show that probability amplification can be done in logarithmic online width. 

Obs: The depth of the circuit C is $O(n)$.