Deluxe starters give you a cool box (and you get black, red, and a few colored beads). The decks aren't really good (the FoTR one was Hobbits/Nazgul).
Anyways, if you want the box or the little card checklist that comes with it, go for it. But wouldn't you rather buy a booster box?
-wtk