The problem of the drunkard in a valley. We consider a Markov chain on a subset of positive integers $S =$ {$0, 1, 2, 3, .......N$}, with transition probabilities defined as follows:
The chain jumps only one unit to the left or right.
$p(i, j) = 0$ if  $|i - j|>1$  
$p(i, i + 1) = (N - i) /N$ , for $i$ in {$1, 2, 3, ....., N-1$}.
$p(i, i - 1) = i/N$ , for $i$ in {$1, 2, 3, ....., N-1$}.
We assume that we have absorbing barriers at $0$ and $N$, so we have $p(0, 0) = p(N, N) = 1$.
What is the expected time it takes for the chain to be absorbed at $0$ or $N$, starting at $i$ in {$0, 1, 2, 3, .......N$}? If $T_i$ is the time it takes for the chain to be absorbed at $0$ or $N$, when starting at $i$, what is $E(T_i)$? 
This Markov chain can be seen as a particular case of a birth and death chain, or as a one dimensional random walk with 2 absorbing barriers and probabilities varying from place to place. 
I would call this the problem of the drunken man in a valley. The closer he gets to the absorbing barriers (the top of the hill), less likely it is that he will continue towards them. Then what is the expected time of the drunkard to reach the top of the hills surrounding him? 
Main question. Is the expected time to absorption polynomial or exponential (in $N$)?
Note that this problem is related to a class of problems of practical interest.
 A: If we make the boundaries at $0$ and $N$ reflecting, rather than absorbing, 
then your random walk is the Ehrenfest urn model. It is well-known that
this Markov chain has invariant distribution $\pi_i={N\choose i}/2^N$ for $0\leq i\leq N$.
In particular,
 the expected time to return to the origin, starting there, is 
$\mathbb{E}_0(T_0)=1/\pi_0=2^N$. This implies 
that the expected time to hit zero, starting at one, is $\mathbb{E}_1(T_0)=2^N-1$.
This is already exponential in $N$, even when the starting point  is right beside the boundary.
Granted, starting at one, we might hit the boundary point $N$ first. 
But I'm willing to bet that this is so unlikely that 
$\mathbb{E}_1(T_{\{0,N\}})$ is exponential in $N$. 

Update: I think I've found a way to make this rigorous.
Create a new random walk on a circle by combining the states $0$ and $N$, call this combined state $b$ (for boundary).
The transition probabilities are all the same except from $b$ you jump to either $1$ or $N-1$ with probability $1/2$.
This chain has invariant distribution $\pi_j={N\choose j}/2^N$ for $j=1,\dots, N-1$ and $\pi_b=2/2^N$.
The expected number of steps to hit the boundary, when you start there, is 
$$\mathbb{E}_b(T_b)=1/\pi_b=2^{N-1}.$$ On the other hand, first step analysis 
gives 
$$\mathbb{E}_b(T_b)=1+\mathbb{E}_1(T_b)/2+\mathbb{E}_{N-1}(T_b)/2=1+\mathbb{E}_1(T_b),$$
where the last equation is by symmetry. Therefore, $\mathbb{E}_1(T_b)=2^{N-1}-1$, which implies 
for the original model that $\mathbb{E}_1(T_{\{0,N\}})=2^{N-1}-1.$
A: If $i \in [0.1N,0.99N]$ then the expected time is exponential, since in order to reach the boundary when you are outside the interval $[N/4,3N/4]$, you move towards the boundary with probability at most than $1/4$. If the probability was $1/4$, then the expected time until reaching the boundary would be exponential in $N$, and hence $E(T_i)$ is exponential in $N$ for $i \in [0.1N,0.99N]$.
A: If $k_i$ is the expected time to absorption conditional on starting at $i$ then $k_0=k_N=0$ and conditioning on the first step gives
$$ k_r = 1 + \frac{r}{N}k_{r-1} + \frac{N-r}{N} k_{r+1}.$$
In principle you can solve these: for $N=4$ you get $0,7,8,7,0$, for $N=5$ you get $0, 15, 35/2, 35/2, 15, 0$, for $N=6$ it's $0,31,36,37,36,31, 0$, and so on.  But a closed form seems hard.
Letting $\delta_i = k_i-k_{i-1}$ makes the recurrence first order: you get
$$r \delta_r = N + (N-r) \delta_{r+1}$$
but it still isn't easy to solve.  Repeatedly substituting gives
$$ \begin{align*} \delta_1 &= N+(N-1)\delta_2 \\
&= N + \frac{N(N-1)}{2} + \frac{(N-1)(N-2)}{2}\delta_3 \\
&= N + \frac{N(N-1)}{2} + \frac{N(N-1)(N-2)}{3} + \cdots \\
&= \cdots
\end{align*}$$
 - binomial coefficients. The $k_i$ are symmetric about $N/2$ so the $\delta_i$ are antisymmetric, and from that you can get $k_1 = \delta_1 = \frac{2^{N-2}-2}{2}=2^{N-1}-1$ as user940 observed. From there you can deduce $k_2 = \frac{N}{N-1}(2^{N-1}-2)$ and so on.  But if you just care about the growth, you know $k_1$ is exponential in $N$ and it's easy to get that the other $k_i$ are larger than $k_1$.
