Kefit needs new shoes. Help him out!

[Kefit]

I've been using the same pair of shoes for over three years now, and I use them for everything I do. They are incredibly ratty, but I am loathe to buy new shoes since I always have such a horrible experience when doing so. The shoe never fits me correctly, and I am somehow never pleased with what I end up with.

I think that the main problem here is that I know absolutely nothing about shoes, or what sort of options I have available to me. So FFR, TEACH ME D:

Oh, and the shoes I get will need to be usable for everything ever - work (which means a lot of walking and some climbing), play (random running around), walking, more walking, and walking/running over fairly rough surfaces from time to time.

I'm sure someone here is a shoe guru. So please, HELPU MI~~~