please to meet you
Does "mucho gusto" always have the "O's"? (versus "A's," mucha gusta)? I say yes.
Does "encatado" vary with who is saying it? i.e. does a female say, "Encatada," and a male say, "Encatado"?
Adjectives agree in number and gender with the nouns/pronouns that they modify. As Lazarus pointed out, when the adjective refers to the speaker/writer (an implied pronoun) this still holds true. Nouns, on the other hand are either masculine or feminine (there are a small number that can be either) and the gender of the noun has nothing to do with the sex of the speaker/listener (unless the noun happens to be another way of referring to the speaker/listener).
"Mucho gusto" is a short for "(Tengo) mucho gusto (de conocerlo/a"), literally "I have a lot of pleasure from meeting you", where "gusto" is a masculine noun that you have, whether you are a man or a woman.
"Encantado/a" is a short for "(Estoy) encantado/a (de conocerlo/a)", literally "I am charmed to meet you" (obviously, "pleased" or "delighted" are better for a translation)., where "encantado/a" is an adjective that agrees with your gender (here, your sex).
Mucho gusto means it's a pleasure. Me gusta... would use an "a" at the end. This means It pleases me... Me gusta a caminar en la mañana. It pleases me to walk in the morning. This form of gusta is from the verb gustar. Hope this helps. I am not an expert by no means but encantado/a is used as a adjective and therefore changes the ending in regards to the noun it modifies. It does mean delighted or pleased and can be used like this-- encantado de conocerle (pleased to meet you).
I think you mean "encantado/a" in place of "encatado". I have only ever heard "mucho gusto" and shall leave the encantado/a question for someone slightly more knowledgeable.