I have a library of 2000 books on the Kindle, and it hasn't slowed it down. I loaded them in batches of 2/300. 4 GB is for the whole Kindle= programthings and so on: it leaves about 3, 09 GB for books/document/music, so Kindle's boost of 3500 books is appopriate.
But take care: indexing makes the Kindle unstable for a few hours. Best is to give the Kindle a rest while indexing and load it (wall charger or on the computer). I made it a habit to load a batch of books at night; leave it on the PC and in the morning indexing had finished and I could do everything I wanted on. Indexing is a weak point.
As for collections; look on the forum, as a lot has been discussed about it.
Good luck; happy reading.