Definitely too tense on the pedals. Your upper air work is fine and most probably because you are more relaxed and you tense up near the ground, a very common fault in the beginning.
It may also be that you are looking way too close in when the ground is close to you, down near your feet. Try driving your car like that and you will be all over the place. Look "down the road" in the hover for a reference.
Lifting your right foot off completely and doing spot turns both left and right using only your left foot will quickly teach you to relax your legs and that you don't need to push hard on the pedals. You will realise how much you are pushing one foot against the other.
If your instructor hasn't mentioned (1) being too tense, (2) where you are looking and (3) tried the left foot only excercise, get a new instructor before deciding to give it away. It is their fault and not yours.
Shoes are also important, but the aircraft is only going to respond to the input you provide. It will never be a good response if you can't see what needs doing and then can't smoothly and accurately provide the input that is required.