Did they do a shell fit?
Do you have a knowledgeable boot fitter you're working with or is it just someone in a ski shop?
Your shoe size is mostly irrelevant since we don't know whether it's US, UK, or something else. Shoe size is not how you determine the correct size for a ski boot. They should have used a Brannock device to measure both feet and then verified it with a shell fit. If all they did was ask your shoe size, I fear your boots are too big. It's easy, for a bootfitter, to make a boot bigger, but it is impossible to make it smaller.
As for footbeds, you can buy heat moldable ones and do it yourself, but if you have any sort of foot problems you should get custom footbeds from a bootfitter.