Complexity of Towers of Hanoi
No, the problem you've described is actually quite easy.  The high-level reason is that the index $i$ is roughly $n$ bits long, so we can actually afford to spend time polynomial in $n$.

Consider the following related problem: Given two integers $n$ and $k$, describe the $k$th move in the solution of the $n$-disk puzzle.  The input size is $\lg n + \lg k &lt; n + \lg k$, but in fact, only the least significant bit of $n$ matters.  So even if $\lg k$ is significantly smaller than $n$, we can solve this problem in time polynomial in $O(\log k)$.

Suppose the disks are numbered from $0$ to whatever in increasing order by size, and pegs are numbered 0=source, 1=destination, and 2=spare.  Let us write $k = (2p+1)\cdot 2^d$ for some integers $p$ and $d$.  Then on turn $k$:


If $d+n$ is odd, then disk $d$ moves from peg $(p\bmod 3)$ to peg $((p+1)\bmod 3)$.
If $d+n$ is even, then disk $d$ moves form peg $(-p\bmod 3)$ to peg $((-p-1)\bmod 3)$.


We can easily compute $p$ and $d$ in time $O(\log k)$ by looping through the binary representation of $k$ from the least significant bit upward.  That's it.

Now suppose you really want the $i$th bit in the output sequence, where $i$ is part of the input instead of $k$.  If every turn is encoded using the same number of bits — specifically, $\lg(n+1)$ bits for the disk number, $2$ bits for the from-peg, and $2$ bits for the to-peg — then we just have to compute the $k$th move, where $k = \lfloor{i/(\lg(n+1)+4)\rfloor}$, and then extract the appropriate bit.  (Notice that $\lg(n+1)+4$ is linear in the input size, since we need to know $n$ to determine the output.)

On the other hand, if we're using a variable-length representation for the disk numbers, then we can find the move number $k$ in polynomial time by binary search.  We need to know  the total number of turns needed to move the top $m$ disks, for all $m\le k$, but this is given by the recurrence
$$
M(m) = 2M(m-1) + (\text{\#bits to record moving disk } m)
$$
which we can evaluate in polynomial time by dynamic programming.  The remaining details are left as a boring exercise for the reader.

(I assume I've made at least one off-by-one or parity error, but hopefully the main idea is clear.)