I came from the same background as you did and I've started tinkering with Arduino this year.
I would recommend a starter kit (I see you've already went in this direction). I can personally recommend this one:
http://www.sparkfun.com/products/10173
What's good about it? It contains:
- the basic stuff (an Arduino, a breadboard, a set of resistors, a bunch of jumper wires),
- a multitude of diverse components;
- and it includes learning materials - an instruction booklet and breadboard overlays.
I would look for these qualities when deciding on a starter kit. Note, by the way, that the learning materials in the aforementioned kit are available online for free (the links can be found on the product page).
Regarding the kit you posted, you don't really need an LCD module for learning about working with Arduino, as it includes a library for bidirectional serial comms.
One more thing: once you catch the Arduino bug, you will eventually need tools. Here's a nice overview. However, the only tool that might be useful to you at the very start is a multimeter and some cutters. You shouldn't need to solder or work with wiring at that point. If the description of a kit you're considering implies it, perhaps start looking for an alternative - unless you already posses experience in those departments.
Finally, consider investing in a storage box with movable separators. Not necessary, but it helps when working on projects :).