Expected minimum influence of a random Boolean function $f\colon\{-1,1\}^n \to \{-1,1\}$
Here's a step in the right direction...

I'll argue that for $p=1/2$, 
you have $1/2 - I_n(1/2) = \Omega(\sqrt{1/2^n})$.

(This is not quite as strong as it should be.
Maybe someone can strengthen the argument to show $\Omega(\sqrt{n/2^n})$.)
Here's a proof sketch.

It suffices to show $1/2 - E_f[\min(\text{Inf}_1[f],\text{Inf}_2[f])] = \Omega(\sqrt{1/2^n})$. We do that.

Note that if $\text{Inf}_1[f]$ and $\text{Inf}_2[f]$ were completely independent, we'd be done because the expectation of the minimum of the two independent sums is $1/2-\Omega(\sqrt{1/2^n})$.  First, we'll argue carefully that the two sums are almost independent.

Consider the universe of points $X=\{-1,1\}^n$.  Call $x$ and $x'$ in $X$ $i$-neighbors if they differ in just the $i$th coordinate.  Say the two neighbors contribute (to $\text{Inf}_i[f]$) if $f(x) \ne f(x')$.  (So $\text{Inf}_i[f]$ is the number of contributing $i$-neighbors, divided by $2^{n-1}$.) Note that, if $x$ and $x'$ are $i$-neighbors, and $y$ and $y'$ are $i$-neighbors, then either $\{x,x'\}=\{y,y'\}$ or $\{x,x'\}\cap\{y,y'\}=\emptyset$.  Hence, the number of contributing $i$-neighbors is the sum of $2^{n-1}$ independent random variables, each with expectation $1/2$.

Partition the universe $X$ into $2^{n-2}$ groups of size four, where $x$ and $x'$ are in the same group iff $x$ and $x'$ agree on all but their first two coordinates. Then for each pair $(x,x')$ of 1-neighbors, and each pair $(x,x')$ of 2-neighbors, $x$ and $x'$ are in the same group.  For a given group $g$ and $i\in\{1,2\}$, let r.v. $c^g_i$ be the number of contributing $i$-neighbors in $g$. Then, for example, the number of contributing 1-neighbors overall is $\sum_g c^g_1$, a sum of $2^{n-2}$ independent random variables, each in $\{0,1,2\}$.

Note that $c^g_1$ and $c^{g'}_2$ are independent if $g\ne g'$. By a case analysis, if $g=g'$, the joint distribution of $c^g_1$ and $c^g_2$ is 
$$\begin{array}{c|ccc}
 &amp; 0 &amp; 1 &amp; 2 \\ \hline
0 &amp; 1/8 &amp; 0 &amp; 1/8 \\
1 &amp; 0 &amp; 1/2 &amp; 0 \\
2 &amp; 1/8 &amp; 0 &amp; 1/8 \\
\end{array}$$

Let r.v. $N=\{ g : c^g_1=c^g_2=1\}$ denote the set of neutral groups. (They contribute exactly their expected amount to the 1-influence and the 2-influence.) The number of contributing 1-neighbors is then
$$|N| + \sum_{g\in \overline{N}} c^g_1.$$

Conditioned on $N$, for each $g\in \overline N$ r.v.'s $c^g_1$ and $c^g_2$ are independent (by inspection of their joint distribution above), so (conditioned on $N$) all r.v.'s $\{c^g_i : i\in\{1,2\}, g\in\overline N\}$ are i.i.d. uniformly over $\{0,2\}$ so, 
$$\textstyle E\Big[|\overline N|- \min\big(\sum_{g\in \overline N} c^g_1, \sum_{g\in \overline N} c^g_2\big) ~\Big|~ N\Big] \ge \Theta(\sqrt{|\overline N|}).$$

Finally, note that each group is neutral with probability 1/2, so $\Pr[|\overline N| \le 2^{n-2}/3]$ is extremely small, say $\exp(-\Omega(2^n))$ (and even in that case the left-hand-side above is at least $-2^n$). From this the claimed lower bound follows...