An $L^0$ Khintchine inequality

OK. Here's a proof that $c > 0.002$. No doubt it can be substantially improved. We can assume the $a_i$ are arranged in decreasing order. Write $a$ for $a_1$.

If $a\ge 1/2$, let $X=a_1\epsilon_1$ and $Y=(1-a^2)^{-1/2}(a_2\epsilon_2+\ldots+a_n\epsilon_n)$ so that $S=X+\sqrt{1-a^2}Y$. Notice that $Y$ is of the form so that the inequality in the question applies.

Now $\mathbb P(|\sqrt{1-a^2}Y|\ge 1-a)=\mathbb P(|Y|\ge \sqrt{\frac{1-a}{1+a}})\ge \left(1-\frac{1-a}{1+a}\right)^2/3=4a^2/(3(1+a)^2)$. Since $a\ge 1/2$, this exceeds 4/27, so that provided $\epsilon_1$ has the same sign as $Y$, the sum is at least 1. This occurs with probability at least 2/27.

If on the other hand $a<1/2$ then we have $a_i^2<1/4$ for each $i$. In particular there exists a partition of $\{1,\ldots,n\}$ into two sets $A$ and $B$ such that $3/8\le \sum_{i\in A}a_i^2\le \sum_{i\in B}a_i^2\le 5/8$. Let $\alpha^2=\sum_{i\in A}a_i^2$ and $\beta^2=\sum_{i\in B}a_i^2$. Let $X=\sum_{i\in A}(a_i/\alpha)\epsilon_i$ and $Y=\sum_{i\in B}(a_i/\beta)\epsilon_i$. Then $\mathbb P(|X|\ge 3/4)\ge 49/768$ by the given inequality. Similarly $\mathbb P(|Y|\ge 3/4)\ge 49/768$. The probability that they both exceed $3/4$ and have the same sign is at least $1/2(49/768)^2$. If this is the case $|S|=\alpha |X|+\beta |Y|\ge (3/4)(\alpha+\beta)$. In the worst case $\alpha=\sqrt{3/8}$ and $\beta=\sqrt{5/8}$, but even in this case the right side exceeds 1.

I would like indeed to improve the lower bound on $c$, to about $0.032$. I'll be using the same notations as in Anthony Quas's answer. As he showed using the result by George Lowther, $$(*)\qquad P(|S|\ge1)\ge\frac{2a^2}{3(1+a)^2},$$ which actually holds for all possible values of $a$ (in $[0,1]$).

The main new ingredient is the following lower bound on $ES^4$:
$$(**)\qquad ES^4=3\Big(\sum_i a_i^2\Big)^2-2\sum_i a_i^4\ge3-2a^2, $$ which suggests that $|S|^2$ must be "large enough with a large enough probability" (as compared with $E|S|^2=1$). On the other hand, $$ ES^4=ES^4\,\mathrm{I}\{|S|<1\}+ES^4\,\mathrm{I}\{|S|\ge1\}\le1 +\sqrt{ES^8\,P(|S|\ge1)}, $$ by the Cauchy--Schwarz inequality; here $\mathrm{I}\{\cdot\}$ is the indicator function. Therefore and in view of $(**)$, $$(***)\qquad P(|S|\ge1)\ge\frac{(2-2a^2)^2}{ES^8}. $$ By the Whittle inequality Whittle, $ES^8\le EZ^8=105$, where $Z$ is a standard normal random variable. So, combining $(*)$ and $(***)$, one has $$ P(|S|\ge1)\ge\min_{a\in[0,1]}\Big(\frac{2a^2}{3(1+a)^2}\bigvee\frac{(2-2a^2)^2}{105}\Big)>0.032. $$

Addendum: As shown in Rademacher-lower, the lower bound $\frac{(2-2a^2)^2}{105}$ on $P(|S|\ge1)$ can be improved to $$\frac{2(1-a^2)^3}{(6+a^2)(5+2 a^2)}.$$ Thus, the lower bound $0.032$ gets improved to $0.043$.

Addendum 2: Instead of the Paley--Zygmund inequality, used by George Lowther to show that $P(|S|>u)\ge(1-u^2)^2/3$ for $u\in(0,1)$, one can use the Cantelli inequality to get $$P(|S|>u)=1-P(1-S^2\ge1-u^2)\ge\frac{(1-u^2)^2}{(1-u^2)^2+E(1-S^2)^2} \ge\frac{(1-u^2)^2}{(1-u^2)^2+2}, $$ since $E(1-S^2)^2=ES^4-1\le2$. Now proceeding as before, one has the lower bound $$\frac{a^2}{(1+a)^2+2a^2} $$ in place of $\frac{2a^2}{3(1+a)^2}$, which results in the improvement of the lower bound on $P(|S|\ge1)$ from $0.043$ to $0.04789$.

In 1996, Krzysztof Oleszkiewicz proved that $c = 1/10$ works. Here is the reference: K. Oleszkiewicz (1996), "On the Stein property of Rademacher sequences", Probability and Mathematical Statistics 16:1, 127-130. The paper is currently available on this page: http://www.math.uni.wroc.pl/~pms/publications.php?nr=16.1