The problem with Hamming distance is that it's bounded above by N, so if you have a subset of F_2^N with Hamming distances in that range, you're not going to be able to embed it in F_2^n for n much smaller than N.
Perhaps more natural is to build in a scaling, so that you want to find an embedding f of the subset S of R^N into R^n in such a way that
d(f(x),f(y)) ~ (n/N)d(x,y).
In other words, given two vectors x and y, you want the proportion of coordinates in which they agree to be more or less left alone by the projection. Then you could try a random projection as in Johnson-Lindenstrauss -- i.e. show that (if indeed this is true) a random choice of one of the N choose n coordinate projections gives you low distortion in this sense, when n is not too horrifically small.