The way I started was with a $18 duemilanove from ebay and a handful of random components and lots of trial and error. I don't really see the need to pay for a uno with a kit and all that because its cheaper to just buy what you need and theres really no huge advantage to the uno over the duemilanove.
To my happy surprise I actually received two arduinos
Can't beat $9...
One of the first things I coded was a multiplexed 8x8 matrix with sound sensitive programs including beat detection. If your unfamiliar with coding I would suggest this because it has a lot of very important concepts such as maximizing speed, dealing with PWM and multiplexing, arrays, beat detection and a bunch of other stuff. I still use a lot of that code in other applications actually, the beat detection I wrote works surprisingly well, I still haven't been able to make it work better. Also coding matrices and visual effects is fun, its like an art form haha.
I used Futurlec to buy components at first but couldn't stand the wait time, digikey is generally good but I only go for them with large orders to offset the higher shipping cost. If you want a lot of any given component like LEDs or something also look at ebay, prices there are often much better than the large suppliers in quantity. Also for power LED type things check dealextreme