After some thought, I guess I'll go with the first argument, that seems plausible (though I don't think it's accidental). As for coating one side with a layer, that seems like a bit too much.
Assuming the second argument is correct, then it's most probable that it doesn't matter which side you use. Because if one side is a 'coated', that 'coat' has got to be safe. Since well, aluminium foil is used pretty much only for packaging food, I don't think people could go about selling Al foil coated with some toxic film for the past couple of decades or so without someone pointing out something very wrong.
Now if it's the first argument, then it still doesn't matter which side you use. Aluminium oxide isn't really as dangerous as out make it out to be, especially if you're dealing with an oxide film that's still on the foil (Hogging a tablespoon of powdered aluminium oxide is another story altogether...). We sometimes call that process (aluminum developing an oxide coat) Passivation, because the foil is rendered 'passive' or 'inert'. Why else do you think it takes so long to get aluminium to react with acids or alkalies?
In a nutshell, regardless of which argument is correct, it'd be perfectly safe to use either side of the foil.
The reflective surface will reflect heat and the matte side will absorb heat. If you're baking or defrosting, the matte side will absorb more radiant heat and reflect less infrared heat while the shiny side will reflect more of both, so it makes more sense to bake and defrost with the matte side facing up. Conversely, during freezing, it makes more sense to reverse the sides as the shiny side face up would reflect heat away from the food.
I've always felt that one of the more practical reasons for creating two visually dissimilar sides on the foil, is to make it easier for you to identify which side you had initially used to wrap some food in. Say, you had just hurriedly unwrapped a cheeseburger and you don't feel like finishing it off. If you re-wrapped using the wrong side, you just get greasy fingers, which is quite annoying.
EDIT: I've read @Vedant's answer and he seems to have provided a good explanation as to why the two surfaces are dissimilar. But I wouldn't entirely dismiss the reason I've mentioned (identification), since, from my personal experiences...I'm pretty sure my keyboard would be covered in grease by now.
But all the same, I've included @Vedant's explanation as well, to give you the complete package.