I use the knot he calls the "Ian Knot" and after about 7 years it's come untied maybe twice.
The easiest thing to learn is, on the "typical knot" most people learn at childhood, if your "loops" stick out up and down instead of at the sides, then you're doing it wrong (tying a granny instead of a square knot) and need to reverse half your technique. Since the first "X" is simpler, the easy path is to just reverse the X you normally do and proceed from there. Suddenly, your shoes will come untied much less.
And yes, I look at peoples shoes for this too... Unbelievably, there is a Ted talk about this