I'm extremely confused. We generally know that for a linear transformation represented by a matrix $T$:
$$P_{C}^{B}T_{B}^{B}P_{B}^{C}=T_{C}^{C}$$ And generally one can multiply a matrix $A$ for example by $P^{-1}$ and $P$ where they matrix $P$ has the eigenvectors as columns and we get a diagonalized matrix $D$ - $$D = P^{-1}AP$$
My question is, are the two formulas related? We know that $$ P_{C}^{B}=\begin{pmatrix}| & | & |\\ \left[b_{1}\right]_{C} & \left[b_{2}\right]_{C} & \left[b_{3}\right]_{C}\\ | & | & | \end{pmatrix}$$
But can I write the $P$_s in $$D = P^{-1}AP$$ in the same way? What will their lower or upper indices be? It is obvious that $A^{E}_{E}=I$ for instance, so that really confuses me. What does it mean to change the basis of a matrix, what index are we talking about?
A diagonalizing change of basis is just a specific kind of change of basis. We usually talk about a square matrix as taking inputs in a basis $B$ and giving outputs in the same basis $B$. A change of basis transformation would switch between bases $B$ and $E$, or the reverse, and be written either $P_B^E$ or $P_E^B$.
Suppose you have a basis $b_1 = (1,1)$ and $b_2 = (1,-1)$. Then the matrix $$P = \begin{bmatrix}1&1\\1&-1\end{bmatrix}$$ will convert the standard basis to the $B$ basis, and its inverse$$P^{-1} = \begin{bmatrix}1/2&1/2\\1/2&-1/2\end{bmatrix}$$ will convert from the $B$ basis back to the standard $E$ basis. Now suppose you have an operator that doubles $b_1$ and triples $b_2$. Its diagonal form is $$D = T_B^B = \begin{bmatrix}2&0\\0&3\end{bmatrix}$$ and its form in the $E$ basis is $$A = T_E^E = PDP^{-1} = \begin{bmatrix}5/2&-1/2\\-1/2&5/2\end{bmatrix}$$ If we had started with matrix $A$ and wanted to diagonalize it, you would need to find out that $(1,1)$ is an eigenvector of $A$ with eigenvalue $2$, and $(1,-1)$ is an eigenvector of $A$ with eigenvalue $3$, construct $P$ and go the other way.
If you want a visual aid to understanding, you can imagine a couple of independent vectors $v_1$ and $v_2$ as arrows, and $Tv_1$ and $Tv_2$ as another pair of vectors. That is a "coordinate free" description of what $T$ does. In order to put numbers on it (besides maybe eigenvalues if you measure lengths and happened to have eigenvectors drawn) you need to add a coordinate system: a grid. You can use a standard grid, or a grid with one axis slanted, or a grid with both axes slanted so the grid is made of parallelograms. The numbers you get simply determine the values you get in $T_E^E$ or $T_B^B$ or $T_Q^Q$ or whatever basis you want.
The two most interesting bases are usually the standard one and the one made of eigenvectors (if it exists) or "as many eigenvectors as possible" plus extra if it doesn't.
Ultimately, the numbers in a vector, the components, are simply a description for a given basis of how many of the first basis vector and how many of the second basis vector and so forth are needed to make the given vector. And the entries of a matrix for $T$ in any given basis can be found using the components of the inputs and outputs.
I'm not sure exactly where your confusion lies, but I hope that helps.