Well than I suppose this is outta my aide. It looks perfect to me, but maybe it just doesn't seem right in gameplay I don't know. If this isn't good enough, than I don't think I can help you. I don't see how it's gonna get much better...
I think the flat foot only looks funny because this is a mario sprite...Nintendo always did 'cartoony' walking animations rather than realistic ones when addressing the mario franchise...