I work for skate warehouse. I have good advice. It's my job, i get asked this question every day at work.
The only sure things in skateboarding are wheels bearings and size of the deck. the other shit people tell you is all opinion.
Indy's are some of the best trucks around but there are other great brands. I have been skateboarding 12 years and i only ride Krux, thunders are great, tensor, indy, thieve. There are other good companies in the end you just gotta try some out and find whats best for you.
As for the deck he is right you're gonna want an 8.0 or larger since you have size thirteen shoes you can ride an 8.5 like I ride an 8 but if I were you I'd go for an 8.125 or an 8.25. Shop decks are fine and supportive, but there is nothing wrong in buying a solid brand name deck, I love habitat and alien, heroin skateboards are tight, stereo, real, i mean the list goes on those are my personal preferences that's another thing about skating you figure out shapes and sizes and nose and tail sizes that you prefer. Oval noses or snubbed noses. That all comes with time, for a beginner go shop deck and play it safe.
DON'T JUST GET BLANK NO BRAND WHEELS
people say "oh you're just beginning you dont need name brand wheels the graphics gonna rub off anyway."
WRONG, blank wheels are cheaply made with cheap urethane, the urethane they use will yellow fast and get flat spots incredibly fast. Just pay the extra ten dollars and buy a set of bones. I shit you not bones is the only wheel I recommend. They last long, never flat spot, stay white, they are the highest quality wheel. as for size of the wheel go with a 53 mm it's a nice all around wheel, on the streets, in the park, or in some deep tranny you will be solid.
Bearings, always swear by bones reds, most consistent long lasting fast bearing ever constructed, they're the shit, literally not worth getting anything else with quality and a price like bones reds bearings. Nothing comes close.
hard ware, don't get colorful ass hardware like some sort of foofy fuck boy, you don't wanna go to the park sucking it up only to have rainbow colored nuts and bolts. The mexican kids will shit on you. I don't care where you live either, there will be some sort of mexican lurking your local park beign a fucker. Thats as certain as the sun will rise tomorrow.
Grip tape, go with MOB baby because it's the grippiest toughest and longest lasting.
I'm trying to remember anything I may have forgotten but I think this is a solid guide for anyone wanting to start out.
If anyone needs skateboarding advice on anything related to skating; shoes to ride, spots nearby, want to share some skate edits, or maybe you want to know how to stomp those bomb ass dank ass nollie tre's with speed and steez in front of hot bitches near your school. Just send me a PM.