The minimum size SD card you can use for Rasbian is 2GB, but it is recommended to get a 4GB SD card or above.
A Class 4 card, which is the minimum recommended has an average read/write speed of 4 MB/sec. If you spend a little extra and buy a Class 10 card, you should find that the boot time is approximately 25% of the Class 4, as it should read at 10MB/sec.
However real world experience has found that that class 4 cards designed for random access perform faster than "faster" class 10 cards which are designed for block reading and writing. See this post by the foundation as to why they have selected a Samsung class 4 card for the NOOBS distribution.
File IO Speed