Usually one foot is larger, and I think the more squished your toes have been, the longer it takes to stretch them out.

You're using the right approach -- just don't push them down all the way at first, and increase the time gradually. For me, even 20 minutes make my feet feel a lot better.