Overrunning First Base
 

How much of a move towards second base must a runner make to be liable to be put out?

For example, if a runner makes a hard step toward the middle of the infield, then starts walking back toward first base, is that enough to be considered not "returning immediately to the base"? Would you call them out if tagged?

Judgment call all the way. If it looked like he was making an attempt at second, then he can be tagged out. If he was merely turning around to go back to first, then he is protected. Like most violations in baseball, you should know it when you see it.

I agree with Steve. In your specific example, a "hard step" would be enough to judge an attempt to second and make the runner liable to be put out.