When can we say that two programs are different?
Q1: There are many notions of program equivalence (trace equivalence, contextual equivalence, observational equivalence, bisimilarity) which may or may not take into account things such as time, resource usage, nondeterminism, termination. A lot of work has been done on finding usable notions of program equivalence. For example: Operationally-Based Theories of Program Equivalence by Andy Pitts. But this barely scratches the surface. This should be useful even if you are interested in when two programs are not equivalent. One can even reason about non-halting programs (using bisimulation and coinduction).

Q2: One possible answer to part of this question is that interactive programs are not algorithms (assuming that one considers an algorithm to take all of its input at once, but this narrow definition excludes online algorithms). A program could be a collection of interacting processes that also interact with their environment. This certainly doesn't match with the Turing-machine/Recursion theory notion of algorithm.