At large $N$, gravity theory becomes weakly coupled is correct as we see from its formula that string's coupling is proportional to $1/N^2$. then how could gauge theory become strongly coupled?
Usually we say there are at least two parameters on either side of the duality. For example, if the CFT is a gauge theory, there are the gauge coupling g and the rank of the gauge group N. Meanwhile, on the AdS side, we may talk about the string coupling g_s and e.g. the string tension or the radius of the compact dimensions. So when we talk about different regimes of the duality, we have to pay attention to what both parameters are doing.