BE manuals tells us that it will only work with CF type II cards, and the voltage must be 3.3v. Most of cards sold on pricewatch don't tell you what the voltage is, and none of them tell you whether it's type I or II. It turns out that both type I and II works on BE, and it turns out that all (most?) the cards sold on Pricewatch are dual 3.3v/5v.
I bought a 512mb kingston card for $25 (in Nov 2005) after rebate. I've heard that 1gb cards work just as well - at this cost there really isn't any reason not to get at least 512mb.
On the other hand, you only really need it for mp3s. You can fit enough books to last you a couple of weeks even without a storage card.