When we randomly initialize the Embedding Matrix with random values, do we need to make sure that the rows are different from other rows so that categorical variables are still distinguishable?

No, in principle embeddings are simply weights, like any other weights in neural nets, so it is fine to have them all randomly initialized (there are of course different methods for that), they will be updated through gradient descent/backpropagation. Also, the embedding matrix is kind of a lookup table, so each category has its own row anyways, even if at the beginning they were to be initialized to the same random values.