Well I will recommend to take the Arduino Duemilanove if you're a beginner and don't plane to make a robot.
The Arduino Duemilanove has lots of memory and it's the newest model also it's the best one.
About the starter kit, this one looks good: http://bit.ly/10iiAW
It has lots of really useful stuff and you could to lots of nice projects.
There is no such thing as "the best board". It depends on what you want to do and what your level is. Here my incomplete criteria collection:
If you are completely clueless --> go for Arduino, it is the standard
If you are cheap --> go for a Freeduino
If you are really cheap and your time does not matter and you know which side of a soldering iron gets hot --> solder it yourself
If you want to use shields --> go for a standard format board
If you want to prototype your own stuff --> go for a boarduino and/or seeduino or some variant of those
If you want to use shields and have standard layout compatibility --> go for seeduino
If you need lots of IO --> go for an Arduinio Mega
If you are experienced with Atmel microcontrollers do not go for the Arduino, take you STK500 and flash it to behave like an Arduino. But then you would not be asking
If money does not matter but time does, then buy professional advice