I am currently also vacationing in Vienna and grew up here. The largest magic shop is Vienna magic http://www.viennamagic.com/
Depending on who is in the store the service can be good or bad, but a visit is worth it. They also have a few unique items they manufacture themselves.
My local shop is Sinaro in the 10. district http://www.sinaro.at/
You will most of the time find Robert Busina the owner who is knowledgeable, friendly and one of the dealers who speak English. The best way to reach it is with U1 to Reumannplatz and then a few minutes walk. And while you are at Reumannplatz you must get ice cream from Tichy. They have the best soft ice cream on earth, no kidding.