I can tell you that these prices can very well be beaten if you're just looking for some display to play and learn with, you'd have to wait a bit longer for cheaper displays to arrive (from China or so).
Yep, You can find 16x2 on ebay for just a couple of USD. The 20x4 are about $10 USD.
If you want to use the LiquidCrystal library that comes with the Arduino IDE,
then the key to finding an LCD will be to get one that uses a HD44780 interface.
On ebay you can search for HD44780 and see several options.
You can also search for "1602 LCD" or "2004 LCD" to see 16x2 or 20x4 LCDs.
The LiquidCrystal library drives the hd44780 LCD interface
using 6 arduino pins in 4 bit mode and 10 arduino pins in 8 bit mode.
If you want to use fewer pins you can use I2C or a TTL serial interface.
There are LCD modules that have I2C or serial interfaces on them.
These will require a different library than the one that comes with the Arduino IDE.
There are also LCD backpacks that can be purchased that will convert the
HD44780 interface of the LCD to i2c or serial.
When using i2c or serial it often isn't quite as "plug and play" as using the HD44780
interface. This is because the HD44780 interface is standardized.
so every LCD that has a hd44780 interface works the same using the same pins.
When using i2c or serial, there is no standard for talking to an LCD so there are many different
ways to talk to the LCD through the module/backpack.
While i2c interface itself is standardized, (the interface between the Arduino and the i2c chip)
how the i2c chip talks to the hd44780 LCD is not standardized.
For example, the i2c backpack can use different i2c chips.
Even using the same i2c chip doesn't guarantee compatibility since the output pins
from the i2c chip may not be wired up to the hd44780 LCD interface the same way.
Because of that it can be a bit challenging to get the i2c interface up and working
initially depending on how much information the vendor supplies.
But it isn't that difficult,
(it requires installing a new library and then configuring the sketch to use it for the hardware)
and it is a one time thing. i.e. once it is done, it will "just work".
So all that said,
using i2c to talk to LCDs is works pretty well and saves pins, particularly if
talking to multiple LCDs since with i2c you only use 2 pins on the Arduino regardless of how many
LCDs you are talking to.
For a super quick & easy plug and play option, you could go with a LCD shield.http://www.ebay.com/sch/i.html?_odkw=LCD+shield&LH_BIN=1&_sop=15&_osacat=0&_from=R40&_trksid=p2045573.m570.l1313&_nkw=Arduino+LCD+shield&_sacat=0
With one of these, you are up and going almost immediately since it works
with the LiquidCrystal library.
Plus, there are some button inputs to play with as well.
I will caution you that usually these shields are not wired up to the Arduino pins
the same was as the LiquidCrystal examples so it won't work "out of the box" with
the LiquidCrystal examples.
However, a simple change to the LCD constructor in the sketch (which specifies the pins)
and the shield works just fine.