I really like Vigleik's answer, but I'll throw in yet another way to look at your original problem. Px = (Px-1+Px+1)/2 is an example of a (discrete) harmonic function; i.e., a function whose value is the average of the adjacent values. In this case, Px is a harmonic function on a chain graph. For purposes of intuition, we can move from a discrete to a continuous line and think about the criterion for a function of one (real) variable to be harmonic: it is harmonic if and only if its second derivative vanishes; i.e., it's linear. This provides some intuition why your solution just linearly interpolates between 0 and 1.
Your general problem of Px,y,p is no longer harmonic, so it will not have as easy a solution, as you may be discovering. For notational simplicity, I'll write Pn for Pn,y,p (preferring n as the index of a sequence to x). If you write down your new recurrence, you will get equations
Pn = (1-p)Pn-1+pPn+1
subject to P0 = 0, Py = 1. We can work with this, or we can use a trick. Let k = (1-p)/p (so p = 1/(1+k)). Then you can verify that
Pn = kPn-1 + 1
satisfies the original equation (with the additional freedom to scale all Pn by a constant factor - we've broken the homogeneity of our original recurrence). [It actually takes some doing to verify this: consider using this new recurrence to write down Pn-Pn+1. When you solve that out for Pn, you retrieve the original recurrence.]
This is much easier to handle, with solution
$P_n = \frac{k^n-1}{k-1}$.
This gives P0 = 0 as desired, but you'll need to scale down all solutions so that Py = 1.
Here's how I interpret your example: there are a bunch of coins (k initially), each being flipped every round until it comes up tails, at which point the coin is "out," And you want to know, after n rounds, the probability that exactly j coins are still active, for j = 0, ..., k. (The existence of multiple players seems irrelevant.)
In that case, this is pretty elementary: after n rounds, the probability of each individual coin being active is p^n, so you have a binomial distribution with parameter p^n, k trials. Since you want to send p to 1 and n to infinity, note that replacing p by its square root and doubling n gives you the same distribution.
Your problem has a surprisingly fascinating generalization, which I believe is called the Galton-Watson process. Its solution has a very elegant representation in terms of generating functions, but I think there are very few examples in which the probabilities are simple to compute in general. Your instance is one of those. (The generalization: at each round, you have a certain number of individuals, each of which turns (probabilistically, independently) into a finite number of identical individuals. If the individuals are coins and each coin turns into one coin with probability p and zero coins with probability 1-p, and you begin with k coins, then we recover your example.)
Best Answer
I can prove that the number actually described by the word problem, which is $$ \prod_{i=0}^{\infty} \left( 1- \frac{1}{2^{2^i}} \right),$$ is irrational, by a method similar to David Speyer's.
Expanding out the product, we get $$\sum_{j=0}^{\infty} \frac{(-1)^{t_j} }{2^j}= 1+\sum_{j=1}^{\infty} \frac{(-1)^{t_j} }{2^j} = \sum_{j=1}^{\infty} \frac{1}{ 2^j} + \sum_{j=1}^{\infty} \frac{(-1)^{t_j} }{2^j} = \sum_{j=1}^{\infty} \frac{1+ (-1)^{t_j} }{2^j} = \sum_{j=1}^{\infty} \frac{1+ (-1)^{t_j} }{2} \cdot 2^{1-j} $$ where $t_j$ is the number of $1$s in the binary expansion of $j$.
Thus the binary digit in the $j-1$th place is $1$ if $t_j$ is even and $0$ if $t_j$ is odd.
Since this sequence is not periodic, the number is irrational.