Consider a vector $\vec{A} = A_x \hat{x} + A_y \hat{y} = A^i e_i$. Intuitively, it seems as though the coordinates ($A_x,A_y$) must transform in the opposite way as the bases ($\hat{x},\hat{y}$). For example if you rotate the bases by some angle, then to get the components in the different bases, you must rotate in the opposite direction to compensate. i.e. if you can write $e'_i = M e_i$, where $M$ is some rotation (or other linear transformation), then $(A')^i = M^{-1} A^i$. And this also seems familiar from my vague memory of covariance vs contravariance in general relativity.
But considering a particular example: $\vec{A} = A_x \hat{x} + A_y \hat{y} = A_r \hat{r} + A_\theta \hat{\theta}$, and the transformation between bases is given by:
$$\pmatrix{\hat{r} \\ \hat{\theta}} = \pmatrix{\cos\theta & \sin\theta \\ -\sin\theta & \cos\theta} \pmatrix{\hat{x} \\ \hat{y}}$$
This gives,
$$\vec{A} = A_r(\hat{x}\cos\theta + \hat{y}\sin\theta) + A_\theta(-\hat{x}\sin\theta + \hat{y}\cos\theta) \\ = \hat{x}(A_r \cos\theta - A_\theta \sin\theta) + \hat{y}(A_r\sin\theta + A_\theta\cos\theta)$$
Doing the same for $\hat{x}$ and $\hat{y}$ shows that the components transform in the same way as the bases, i.e. $A_r = A_x \cos\theta + A_y \sin \theta, \,\,\, A_\theta = - A_x \sin \theta + A_y \cos\theta$, instead of transforming in the inverse manner.
Am I doing something wrong here? Or are the components and bases supposed to transform in the same way?
You are discovering the wonders of the contra-gredient transformation. If you write a vector and its basis representation as $$ v=(e_1,...,e_n)\pmatrix{v^1\\\vdots\\v^n} $$ then you can insert $I=M^{-1}M$ in the middle to get that the transformation matrix of the basis tuple is the inverse of the transformation matrix of the coordinate vector.
Now if you arrange the basis tuple also formally as column vector, the transpose of the row above, then the corresponding transformation matrix is the transpose of the inverse, $M^{-\top}$. For orthogonal matrices this is, by definition, the original matrix $M$.
One has to be careful to distinguish the transformation of the vectors by a linear map on the vector space from transformations of the basis tuple, like $$ \phi(v)=(\phi(e_1),...,\phi(e_n))\pmatrix{v^1\\\vdots\\v^n} =(e_1,...,e_n)M_\phi\pmatrix{v^1\\\vdots\\v^n}. $$ or $(v')^i=(M_\phi)^i_jv^j$, which is also valid for isomorphism that are interpreted as coordinate changes.
In that sense, it is ambiguous to write $(A')^i=M^{-1}A^i$, as in your context this connects a column vector map with linear functionals, which do not have a natural connection. What you probably mean is $(A')^i=(M^{-1})^i_jA^j$ with the implied summation.