Thru-hiking: I'm of absolutely no help.

Snickers: Try Paydays - the only thing you don't get is the chocolate. I pretty much skip the chocolate in Ohio in the summer for the same reason you discovered. However, year-round I do take trail mix with M&Ms in it, and they seem to hold up pretty well. I've never had the outside shell actually melt, though the inside doesn't always taste "solid" when you bite into them.