I wrote a Maple program in 2003 which computes $P(\alpha)$ (both the "upper" and "lower" values) for a given rational number $\alpha$, much in line with the method described by Johan. I think I was able to compute it for all $\alpha=a/b$ for integers $1\le a\lt b\le 300$ in a couple of hours, so the program could probably compute fairly good approximations to $P(1-2/\log_2(p))$ when $p$ is not too large. (Edit: When $p$ is large, $1/2$ will be a very good approximation. For example, if $p\gt1000$ then $0.499\lt P(1-2/\log_2(p))\lt1/2$.)
I didn't publish any of this, but much of it is contained in the article "The Maximum Average Gain in a Sequence of Bernoulli Games" by Wolfgang Stadje (American Mathematical Monthly, December 2008).
EDIT: Since I don't have access to Maple anymore, I translated the program to Matlab:
function p=p(s,t);
d=gcd(s+t,2*t);
s=(s+t)/d;
t=2*t/d;
pol=zeros(1,t+1);
pol([1 s+1 t+1])=[1 -2 1];
r=roots(pol);
[rsort,i]=sort(abs(r));
p=1-prod(abs(1-r(i(1:t-s))));
The program computes $P(s/t)$ for integers $0\lt s\lt t$, by computing $1$ minus the product of $1-r$ for those zeroes $r$ of $z^{2t/d}-2z^{(t-s)/d}+1$ that have absolute value less than $1$ (there are $(t-s)/d$ of them), where $d=\gcd(s+t,2t)$.
By the way, in my notes I found the lower bound $P(\alpha)\ge A$, where $\alpha=1-\frac{2\log A}{\log(2A-1)}$, with equality for $\alpha=(k-2)/k$. I think Johan was involved in obtaining this bound.
EDIT (May 14): So, here is a fairly detailed proof of the formula used in the program above.
Lemma 1. For integers $0\lt 2b\lt a$, the polynomial $g(z)=z^a-2z^b+1$ has no multiple zeros and exactly $b$ zeroes inside the unit circle.
Proof. If $g(z)=g'(z)=0$ then $z\ne 0$ and
$$0=g'(z)=az^{a-1}-2bz^{b-1}=z^{b-1}(az^{a-b}-2b),$$
so $az^{a-b}-2b=0$. Hence, $0=g(z)-g'(z)*z/a=1-2(1-b/a)z^b$ so that $|z|^b=\frac1{2(1-b/a)}=\frac a{2(a-b)}$. Also, $az^{a-b}-2b=0$ so $|z|^{a-b}=2b/a$. This implies that
$$\left(\frac a{2(a-b)}\right)^{a-b}=\left(\frac{2b}a\right)^b.$$
This can be rewritten as $2(1-b/a)^{1-b/a}(b/a)^{b/a}=1$. But it is easily checked that $2(1-y)^{1-y}y^y\gt1$ for $0\lt y\lt1/2$, a contradiction.
The second part can be proved by a straight forward application of Rouché's theorem.
Lemma 2. Suppose that $\sum_{i=1}^kA_ir_i^{-j}=1$ for $1\le j\le k$. Then $\sum_{i=1}^kA_i=1-\prod_{i=1}^k(1-r_i)$.
Proof. The equations can be seen as a system of linear equations in $A_1,\dots,A_k$, and the result can be obtained by using Cramer's rule and Vandermonde determinants. I skip the details. (Actually, I think I had a simpler proof of this lemma, but I could neither find it in my notes, nor figure it out right now.)
Now, let $L=\max_{n\gt0}{S_n/n}$, so that $P(\alpha)=P(L\gt\alpha)$. Also, let $Y_i=(X_i+1)/2$ and $T_n=\sum_{i=1}^nY_i$ (so that $T_n$ is a random walk with steps $0$ and $1$ instead of $\pm 1$). (The main reason for this is that my original result was for $T_n$, but I also think that the formulae get a little simpler in this case.)
Let me restate the result I am going to prove:
Theorem. For integers $0\lt s\lt t$, $P(s/t)=1-\prod_{i=1}^{t-s}(1-r_i)$, where $r_1,\dots,r_{t-s}$ are the zeroes of $z^{2t}-2z^{(t-s)}+1$ that have absolute value less than $1$.
Proof. Let $M=\max_{n\gt0}{T_n/n}$ and $Q(\alpha)=P(M\gt\alpha)$. I will prove the corresponding result for $Q(s/t)$, and then translate it to $P$, using the fact that $T_n=(S_n+n)/2$ which implies that $P(\alpha)=Q((\alpha+1)/2)$.
Suppose then that $1/2\lt s/t\lt1$ and consider $Q(s/t)$. Just as Johan did, we define another random walk $U_n=\sum_{i=1}^nZ_i$ with steps $Z_i=s$ or $Z_i=s-t$ so that $Q(s/t)$ equals the probability that $U_n$ will ever reach $-1$, define $f(j)$ as the probablity that $U_n$ will reach $-1$ when it is currently at $j$, and find that $f(j)=f(j+s)/2+f(j+s-t)/2$ for $j\ge0$. The characteristic equation of this recursion is $g(z)=z^t-2z^{t-s}+1=0$. By Lemma 1 and since $f(j)$ tends to $0$ as $j$ tends to infinity, we must have $f(j)=\sum_{i=1}^{t-s}A_ir_i^j$, where $r_1,\dots,r_{t-s}$ are the (necessarily simple) zeroes of $g(z)$ inside the unit circle. Since $f(j)=0$ for $s-t\le j\le -1$, Lemma 2 implies that $Q(s/t)=f(0)=\sum_{i=1}^{t-s}A_i=1-\prod_{i=1}^{t-s}(1-r_i)$.
Now, if $0\lt s/t\lt1$ then $P(s/t)=Q((s+t)/(2t))$, which, by what we have just proved, equals $1-\prod_{i=1}^{t-s}(1-r_i)$, where $r_1,\dots,r_{t-s}$ are the zeroes of $z^{2t}-2z^{t-s}+1$ inside the unit circle. This concludes the proof.
1) I believe it is possible to obtain $P(M_n<a\ | \tau>n)$, where $\tau:=\inf\{n\ge 1: S_n\le 0\}$ in more or less explicit way only for the case of the simple random walk. These computations can be found in Billingsley, Convergence of Probability measures, Chapter 2.11. For large $n$ these computations become universal as you can apply FCLT, see below.
2) Generally, one can use Brownian motion approximations as was suggested by fedja. Mathematic justification is given in the references below. Before going into this I will say a few words about conditioning of random walks to stay positive.
There are two ways to condition random walk to be positive. First way is to condition on $\{\tau>n\}$, where $\tau:=\inf\{n\ge 1: S_n\le 0\}$. Second way, is to ''condition'' on $\{\tau=\infty\}$. Here you cannot use direct conditioning as $\mathbf P(\tau=\infty)=0$ (for the zero-mean finite variance random walk). So, the way to proceed is to use Doob's $h$ transform. As a result one obtains a Markov chain (Lamperti Markov chain, in fact) which is a discrete-time analogue of Bessel process.
Now I can move on to approximations as $n\to\infty$.
a) When $a$ is of order $\sqrt n$, you need to use corresponding Functional Central Limit Theorem (FCLT). You need functional central limit theorem as the maximum depends on the whole trajectory of the random walk.
The way to use functional limit theorems is described in the above Billinsley's book, you can see an example for unconditioned random walk in Chapter 2.11.
For the first type of conditioning FCLT is proved in Iglehart, 1974, Functional Central Limit Theorems for Random Walks Conditioned to Stay Positive (doi:10.1214/aop/1176996607), see also Bolthausen, 1976, On a Functional Central Limit Theorem for Random Walks Conditioned to Stay Positive. Conditioning of the second type was considered in Bertoin and Doney (1994), On Conditioning a Random Walk to Stay Nonnegative (doi:10.1214/aop/1176988497). FCLT for the second type of conditioning can be found in Caravenna, Chaumont (2008), Invariance principles for random walks conditioned to stay positive (doi:10.1214/07-AIHP119). Finally, in higher dimensions you can use FCLT from http://arxiv.org/abs/1110.1254.
b) When $a$ is much larger then $\sqrt n,$ then $\mathbf P(M_n<a\ |\ \tau>n)\to 1$.
c) When $a<<\sqrt n$ you are dealing with small deviations probability.
If you write $\mathbf P(M_n<a | \tau>n)=\mathbf P(M_n<a , \tau>n)/\mathbf P(\tau>n)$, then approximation for $\mathbf P(\tau>n)\sim Cn^{-1/2}, n\to\infty$, and
$$
\mathbf P(\tau>n, M_n<a)=\mathbf P(\mbox{random walk $S_k$ stays in (0,n) for all } 0<k\le n)
$$
Now, if $a\sim An^{1/2-\delta}$ for $\delta\in(0,1/2)$ you can split this trajectory in $n/a^2$ parts of length $a^2$ and use independence to obtain estimate
$$
\mathbf P(\tau>n, M_n<a)\le \left(\mathbf P(\mbox{random walk $S_k$ stays in (0,2a) for all } 0<k\le a^2)\right)^{n/a^2}
$$
Now, the probability inside the parenthesis is on the right scale and you can apply the FCLT to get
$$
\mathbf P(\mbox{random walk $S_k$ stays in (0,2a) for all } 0<k\le a^2)\to C(A)\in(0,1).
$$
This results in the following upper bound
$$
\mathbf P(\tau>n, M_n<a) \le C(A)^{n/a^2}\approx C(A)^{n^{2\delta}}.
$$
As $C(A)$ is in $(0,1)$ this probability is quite small. .
Best Answer
In fact $S_d$ does not converge to zero when $d\to\infty$, at least if $a_x=1$ for every $x$. Here is a proof.
For every $x$, $G_d(x)=P_0^{(d)}(\mathtt{hit}\ x)G_d(0)\le G_d(0)$ hence $G_d(x)^2/G_d(0)\le G_d(0)$. For every $z$ in $[0,G_d(0)]$, $\sqrt{1+z}-1\ge c_dz$ with $$ c_d=\frac1{G_d(0)}[\sqrt{1+G_d(0)}-1]=\frac1{\sqrt{1+G_d(0)}+1}. $$ Hence, for every $(a_x)$, $$ S_d\ge c_dT_d,\quad\mbox{with}\ T_d=\sum_xa_xG_d(x)^2/G_d(0). $$ In the special case where $a_x=1$ for every $x$, by reversibility, $$ \sum_xG_d(x)^2=\sum_{i,j}\sum_xp_i^{(d)}(0,x)p_j^{(d)}(x,0)=\sum_{i,j}p_{i+j}^{(d)}(0,0)=\sum_{i}(i+1)p_i^{(d)}(0,0), $$ hence $$ \sum_xG_d(x)^2>\sum_{i}p_i^{(d)}(0,0)=G_d(0). $$ In particular, $T_d>1$. Now $G_d(0)$ is a nonincreasing function of $d$ hence $c_d\ge c_5$ for every $d\ge5$ and $S_d>c_5$ for every $d\ge5$.
Edit Much simpler: if $a_x\ge0$ for every $x$, then $S_d>a_0(\sqrt{1+G_d(0)}-1)$ and $G_d(0)>1$ hence $S_d>a_0(\sqrt2-1)$.