personally, unless you are fixated on "shields", i think pro-mini is the best target for those starting out. not only 1/10th the cost of the huge boards like duemanilove or uno but actually more signal pins available. very friendly and standardized pin arrangement compared to those of the big brothers. much easier to build from scratch too.
admittedly nice being able to plug in a new chip on those big socketed boards but pro-mini is so cheap at $2-$3 shipped dollars its almost not worth it.