Arduino Starter Kit Suggestions

+1 for the servo - this is a must.
Small vibration motors are cheap and fun, too.
A Wii nunchuck clone is cheap (9 EUR) and offers a lot.