Generate Hofstadter's Figure-Figure Sequence

CJam, 38 30 29 21 bytes

li_3*,2>\{(_pX+:X-}*;

Try it online.

How it works

li                     " Read an integer N from STDIN.              ";
  _3*,2>               " Push S := [ 2 3 ... (N * 3 - 1) ].         ";
        \{        }*   " Do the following N times:                  ";
          (            " Shift an integer I from S.                 ";
           _p          " Print a copy of I, followed by a linefeed. ";
             X+:X      " Execute X += I. (X is initialized to 1.)   ";
                 -     " Remove X from S.                           ";
                    ;  " Discard S from the stack.                  ";

Example run

$ cjam <(echo 'li_3*,2>\{(_pX+:X-}*;') <<< 20
2
4
5
6
8
9
10
11
13
14
15
16
17
19
20
21
22
23
24
25

Haskell, 67 61 60 56 55 53 characters

g n=take n$2:4:h
a#(x:s)=[a..x-2]++x#s
h=5#scanl(+)8h

back to the first algorithm.

this solution computes the complement sequence by summing the starting elements of the sequence. it then computes the sequence as all the numbers between the complement's sequence numbers.

(#) is the function that calculates the numbers between the complement sequence.
h is the sequence itself.
g is the function that answers the question.

the g function is defined to just take the needed amount of elements from h.

subtleties:

h is actually the figure figure sequence except for the first 2 elements.
not the complement sequence is computed, but the complement sequence with added 1 for each element.
these two subtleties are the reason scanl(+)8h (which is the code for the complement sequence (except for the first 2 elements) with added 1's) has 8 in it. it is for the third element of the complement sequence with 1 added to it.
the reason the computation is not missing the first two elements is because they are added in g in 2:4:h.

example:

>g 50
[2,4,5,6,8,9,10,11,13,14,15,16,17,19,20,21,22,23,24,25,27,28,29,30,31,32,33,34,36,37,38,39,40,41,42,43,44,46,47,48,49,50,51,52,53,54,55,57,58,59]

Ruby, 54 48

f=->n{x=1
b=*2..n*n
n.times{b-=[x+=p(b.shift)]}}

Demo

Edit: Golfed this a bit more once I realized I don't need to hold the full complement sequence in memory. Here's how it works now: We use x to keep track of the largest computed number in the complement sequence, and b is a pool of candidates for the sequence. n times, we output the smallest remaining element in b and add it to x to compute the next number in the complement sequence. Then we remove both numbers from the pool of candidates, so we're always outputting the smallest number that wasn't already added to either sequence.

Ruby golf tricks: Stabby lambda syntax is shorter than a method definition. The requirement that output is given to STDOUT instead of as return value inspired me to use the fact that the return value of p(x) is x, which I don't normally remember because it's not the case in the Ruby version used in Anarchy Golf.