The etymology of a and in is simple: they come from Latin ad and in.
This partly explains why we use both a and in to denote direction. But there's also da (which comes from Latin de) and probably only someone really expert in the history of Italian can explain the last preposition.
In Latin ad meant go towards some place, but not necessarily entering it. In the entry ad of Lewis and Short we find
As antith. to ab (as in to ex), in a progressive order of relation, ad denotes, first, the direction toward an object; then the reaching of or attaining to it; and finally, the being at or near it.
Conversely, in implies entering: the entry for in has
I. in, within, on, upon, among, at; into, to, towards.
I. With abl.
II. With acc.
A. In space, with verbs of motion, into or to a place or thing (rarely with names of towns and small islands;
So the Italian usage with towns and small islands is a direct descendant from Latin. A small island is probably identified with its main village or port, so in was felt inappropriate. A big island like Sicily had many towns and a vast land, so in was better suited.
We have vado a casa because one's home is not really a building, but something more intimate. We can and do say vado in casa, for example when I'm in my garden and want to say I'm going into the house. Conversely, vado in ufficio or in chiesa because we enter a building.
My feeling is that with scuola and teatro we don't identify them with a building, so they're abstractions, unless a particular school or theater is specified; not with cinema, probably because it's a recent addition to the language. Here are some examples:
- vado a scuola, vado al liceo Fermi
- vado a teatro, vado al teatro alla Scala
- vado al cinema, vado al cinema Altino (not any more, actually, it has been closed for many years)
For countries it's normally in, but small countries often want a: vado a San Marino (but nel Lichtenstein and nel Lussemburgo).
Side note. As Mauro Vanetti brilliantly remarks in comments, it's not easy to know when an island is to be considered small. For instance, Cyprus is rather larger than Corsica, but we say
a Cipro and in Corsica
so Cyprus is small and Corsica is big, according to the ‘rule’. Also Ceylon is considered small (although being much larger than Sicily, 65 610 km² against 25 711 km²), but it becomes a big island when called Sri Lanka. And il Madagascar follows neither pattern, because it wants the article: maybe, at 587 041 km², it's too big even for an island; but no, Greenland is even bigger (2 166 086 km²) and we say in Groenlandia. Other examples are nel Borneo (743 330 km²) and a Sumatra (473 481 km²): while Borneo is undoubtedly a big island, it's difficult to believe that Sumatra is small.
Toponyms are always a source for controversies, finding one's way in them is always a problem.