There are lots of Arduino starter kits available, but none of them cover my specific starter needs. So I decided to pick one that more or less has the basic component set, and I filled it up with a few other components that I plan on using in the very near future.
First the obvious, I’ll need an Arduino board. For this sake I’ve chosen the Arduino Uno Rev 3 as that is the most popular board available. This way it will be compatible with most of the projects one can find on the internet. Recently the newer Leonardo has become available, and I’m pretty sure that this new board is better than the Uno, but it would also complicate things for a beginner like me.
The kit I chose was just one that was in stock 
It had already an Uno R3 in it, a breadboard and assorted jumpwires, some resistors, some extra LEDs, switches and a bunch of other commonly used components in electronics.
For my personal needs, I added some extra LEDs (you can never have enough LEDs), some 7-segment LED numeric diplays, a LDR, an IRDA LED, a temperature sensor. That should get me started. Now why does it always take so much time for delivery? I’m already waiting a whole day 