What's the difference between Vodka and Moonshine? With the legalization of moonshine in many US states I've been wondering what are the big differences between Moonshine and Vodka?

Both are clear spirits made from whatever grains/starches are available.  Both can be fairly high proof.

Is it all just an Appalachian that is tied to their origin?
Generally, when people refer to "moonshine" and they are referring to what can be purchased legally, they are really referring to "white whiskey" (a.k.a. un-aged whiskey), or whiskey that has not been aged in an oak barrel.

Most whiskey is fermented from either all-corn, or corn and an other grain (like rye), but there are some boutique type whiskeys that use other grains like quinoa, spelt, flax, etc.  Technically any grain can be used to make whiskey, but it doesn't become "whiskey" until it has been placed in an oak barrel.  There are only a few other "rules" like the proof at which it is distilled. Whiskey has to come out of the still at 95% ABV (190 Proof) and then cut with water to nothing lower than 40% ABV (i.e. 80 Proof or higher).

Vodka can be made from corn, but unlike whiskey, it can be made from really anything that can be fermented.  Some of the most common starts for Vodka are potatoes, wheat, rye, and a few other grains, but Vodka can be made from virtually anything else that can ferment like grapes (Ciroc vodka), tomatoes, cucumbers, donuts, you name it. I have seen almond vodka and even milk vodka (as in vodka fermented from almonds and from milk respectively).  Vodka has to come out of the still at >95% ABV, but as long as it is cut with water to at the minimum of 80 poof (40% ABV) or higher, it's vodka. No matter what it started with.

The same exact corn "vodka" can be called whiskey it is comes out at the 95% ABV and then is placed in oak barrels. Note that I wrote "placed" and not "aged" in oak.  Whiskey has no age requirement, so the "white whiskeys" you see that do not read "moonshine" have at least touched oak.  If you see that the label reads "moonshine whiskey", it has touched oak too, if it just reads "moonshine" and has not ever touched an oak barrel, then technically is it strong grain vodka, but "moonshine" sounds more renegade I suppose. Corn "vodka" that comes out of the still at 96%ABV or higher, but doesn't touch oak is still Vodka, but technically could also be called "Moonshine".

Whiskey can be called "bourbon" if it is made in the USA, from 51% corn. It has to come out of the still at no more than 160 proof/80%ABV and it goes into the barrel at 125 Proof (62.5%ABV), and it has to be in the oak for at least 4 years in bonded warehouses under the U.S. government record. Thanks to the Bottle-in-bond Act of 1897.