Get the plain garden variety Uno (or its previous model Duemilanove) - this will last you a long time for all sort of experiments. Apart from the board you'll need the USB cable and some "basic" electronics - a couple of LEDs, some resitors a sensor or two a couple of transistors. Also a breadboard where you just plug things in and a set of jumperwires is almost essential to start. A starter-kit will usually include all this. It really doenst matter where you get it. The software (compiler uploader) is free to download.
Welcome to the world of electronics and where your programs interact with real things!