Subset on boolean cube with largest sum of biases
It will be slightly cleaner to replace $\{0,1\}^n$ with $\{-1,1\}^n$, and to normalize your function $\tilde{p}_i$ so that we get the $i$'th Fourier coefficient
$$
\hat{p}(\{i\}) = \mathbb{E}[x_i p].
$$
Let $\sigma_1,\ldots,\sigma_n \in \{ \pm 1 \}$. Then
$$
\sum_{i=1}^n \sigma_i \hat{p}(\{i\}) = \mathbb{E}\left[\left(\sum_{i=1}^n \sigma_i x_i\right)p\right].
$$
If we define a function
$$ q(x_1,\ldots,x_n) = p(\sigma_1 x_1, \ldots, \sigma_n x_n) $$
then $q \in [0,1]$ and
$$
\sum_{i=1}^n \sigma_i \hat{p}(\{i\}) = \mathbb{E}\left[\left(\sum_{i=1}^n x_i\right) q\right].
$$
Under the constraint $q \in [0,1]$, the right-hand side is clearly maximized when
$$
q = \begin{cases} 1 &amp; \text{if } \sum_i x_i &gt; 0, \\
0 &amp; \text{if } \sum_i x_i &lt; 0, \\
\ast &amp; \text{if } \sum_i x_i = 0, \end{cases}
$$
where $\ast$ means that the value doesn't matter. In other words, $q$ is the majority function, and so
$$
\begin{align}
\sum_{i=1}^n \sigma_i \hat{p}(\{i\}) &amp;\leq 2^{-n} \sum_{k \geq n/2} (k-(n-k)) \binom{n}{k} \\ &amp;=
2^{-n} n \sum_{k \geq n/2} \binom{n-1}{k-1} - 2^{-n} n \sum_{k \geq n/2} \binom{n-1}{k} \\ &amp;=
2^{-n} n \binom{n-1}{ \lceil n/2 \rceil - 1 } \\ &amp;=
2^{-n} n \binom{n-1}{ \lfloor n/2 \rfloor }.
\end{align}
$$
Therefore
$$
\sum_{i=1}^n |\hat{p}(\{i\})| \leq \max_\sigma \sum_{i=1}^n \sigma_i \hat{p}(\{i\}) \leq 2^{-n} n \binom{n-1}{ \lfloor n/2 \rfloor }.
$$
Furthermore, this is achieved for the majority function.