I think of vice as meaning someone who can take over if the boss is unable to. Usually there is just one, unless they have a specific duty (like vice president of marketing in a company), in which case it's more like they are in charge of a department. To me, deputy means someone who has the authority to act for the boss, like a deputy sheriff has the powers of a sheriff to arrest people, etc. There can be a lot of deputies.