I teach CS at a university, often including introductory courses. Regarding FOSS, what message(s) is/are the most vital to communicate to people who are writing computer programs for the first time?

Not part of your question -- but you may want to seriously consider the perk of having FREE wireless internet access that works anywhere in the world (if there is cell phone coverage). I took my kindle DXG and it was amazing to be able to check/send gmail from Tanzania, Kenya, and even Amsterdam along the way. I love the DXG and it's been pretty rugged for me over the last year. I think if you are a hacker enough you can SSH from it to EC2 computers.

Try http://cscircles.cemc.uwaterloo.ca/ and http://thinkcspy.appspot.com/build/index.html the latter is an interactive version of the famous "thinkpython" book. They both have structured curriculum and interactive exercises starting from ground[0].

It's a case of the Traveling Salesman Problem http://en.wikipedia.org/wiki/Travelling_salesman_problem On the one hand it is the special case with Euclidean 2d distances (more or less, depending on hills). But also, it is the special case where all point-point distances are equal, depending on what exactly you meant by 'grid', which is called Graphical TSP. "Computer search algorithms" is a little bit of a weasel word... but as far as I know TSP instances are exactly solved in practice on moderate-size instances using integer linear programming (ILP) techniques, the work of Bill Cook and co-authors is likely useful. From a theoretical (but not so important) perspective: the 2d Euclidean problem is NP-complete but admits an "approximation scheme." I am not sure about the doubly special case you present, but my gut feeling would be it's also NP-complete.