I had; and to a certain degree, still have this issue.

But I got my rate of doing the "get-past-you shuffle" down quite a bit after learning a simple trick.

While I avoid eye contact, most people do not. Most people, when they see an on-coming person, judge which side (left/right) to pass them by looking at their gaze.

The trick is to look in the direction you want to pass the other person in. So if you're going to take the left side, look to your left.

Most people will then pass you on your right side.