Replicant

The Nexus S/Galaxy S are the cheapest phones, but is not the best (in terms of how many hardware features are supported, how fast it is and isn't the best for security either).
I'd recommend the Galaxy S2, which should be less expensive nowadays than it used to be (I guess you can find one for about EUR 200).

I meant cheapest and easiest to find on the internet. Considering that the supported smartphones have several versions that aren't compatible, not to mention the imcompatible knockoffs on some sites.

I strongly recommend the Nexus S. I got mine for $100 from Craigslist, and I got the cable and a spare battery that had never been charged from the deal. The Nexus S is also the easiest phone for installing Replicant IMHO: all you have to do is download the images and issue a few terminal commands, and you're done.

If your budget permits it, I think it's wiser to use something a bit newer, like the Galaxy Nexus or Galaxy S2/Note phones, since they are faster and will more certainly make it to new Replicant versions. I'm not saying we are going to drop the Nexus S anytime soon, but it's getting slower and slower, especially on Replicant 4.2.

But how do I know what is a knockoff on Ebay or Craigslist? Are there questions I can ask to make verification of the product easier? You are answering the first question i have (which phone to get) but not the second (best, most reliable place to buy), not to mention the third question that I just asked in this post. What should I do so I can avoid incompatible knockoffs?