To "start" using the arduino, all you need is the board ($35 or so) and a USB cable. With that you can make the LED on the board blink (yay!). Then add your own LEDs, a button or two, turn them on and off.
To use sensors, chips, or interface with most other components, it's really a lot easier to put them (and any needed other components) on a breadboard. I like the proto shield offered by www.adafruit.com; you do have to solder it together but it's pretty simple.
Adafruit Proto Shield for Arduino Kit [v.5] : ID 51 : $15.00 : Adafruit Industries, Unique & fun DIY electronics and kits
Add tiny breadboard:
Tiny Premium Breadboard : ID 65 : $3.95 : Adafruit Industries, Unique & fun DIY electronics and kits
A set of jumper wires (or three) is really handy; so the starter kit isn't that bad a deal:
Adafruit Metro 328 Starter Pack : ID 68 : $44.95 : Adafruit Industries, Unique & fun DIY electronics and kits
I'm interested in the opposite question. What do I need to get started with max/msp? Do I have to buy the environment? I guess I can try it for 30 days for free, but I'm afraid I'd like it and then be obligated to spend the $500 (ouch!).