I sympathise! It's easy to get confused at first, since the concepts of coordinates and underlying vector space coincide in first example we're exposed to.
Think of the Euclidean plane, as existing independently of coordinates. Euclidean 2-space is (or can be defined/described as) an affine space, which is a mathematical structure consisting of a set of points, \mathbb{E}^2, a set of displacement vectors (one representing each possible combination of a direction and a distance in the plane), \mathbb{V}, and rules relating points to displacement vectors:
(1) For any pair of points, P and Q, the difference, Q - P = v is a vector pointing in the direction from P to Q, and whose length is the distance between P and Q.
(2) If Q - P = v, then P + v = Q.
Notice that every point of the Euclidean plane is equivalent, in the sense that it has no special point we can call the origin. It has lots of symmetry: we can translate, reflect or rotate it, and it looks exactly the same.
Euclidean 2-space has one other important feature, a function called an inner product, g : \mathbb{V} \times \mathbb{V} \rightarrow \mathbb{R}, which means that it takes two vectors from the set \mathbb{V} and outputs a real number. It obeys certain axioms, and gives allows us to define length and angles. It also goes by the names dot product and scalar product. To get this function up and running we need to give it a scale. We can do this by picking a pair of points, P and Q, and defining our unit of distance as the distance between these points:
d(P,Q) = d(Q,P) = \sqrt{g(Q-P,Q-P)} = \left \| Q-P \right \|,
where d:\mathbb{E}^2 \rightarrow \mathbb{R} is the distance function, defined thus for Euclidean space. \left \| Q-P \right \| is called the length or magnitude or norm of the vector Q - P. It doesn't matter what points we chose, as long as they're different from each other; if we want to change to a new unit, we can define it as a multiple of this unit, or, equivalently, with another pair of points.
Now coordinate systems. These are functions from a subset of \mathbb{E}^2 (which might be the whole of \mathbb{E}^2) to the real numbers, \mathbb{R}. In two dimensions, we need a coordinate function, \phi, with two components:
\phi_1 : \mathbb{E}^2 \rightarrow \mathbb{R}^2,
\phi_2 : \mathbb{E}^2 \rightarrow \mathbb{R}^2.
Suppose we've chosen to define a particular Cartesian coordinate system. We pick an arbitrary point to be the origin of our coordinate system. Another point indicates the direction of the x axis, and a third that of the y axis, giving us an orientation, as Phrak described. Now, for any point, P,
\phi_1 (P) = x,
\phi_2 (P) = y.
Each component defines certain curves, called coordinate curves, which are just its level curves; that is, subsets of the domain, \mathbb{E}^2, for which the output of the component function is a particular constant. In Cartesian coordinates, the coordinate curves of the first component, \phi_1, are lines perpendicular to the x axis. The coordinate curves of the second, \phi_2, are lines perpendicular to the y axis.
The whole coordinate function maps the Euclidean plane to the set of pairs of real numbers, \phi : \mathbb{E}^2 \rightarrow \mathbb{R}^2. This is true of any coordinate function, not just Cartesian coordinates, but for other systems, we can't necessarily use the range as (the underlying set of) a vector space in the usual way.
For example, we could just as well have started by chosing a polar coordinate system. Then the coordinate function has components
\psi_1 (P) = r,
\psi_2 (P) = \theta.
Now the coordinate curves (level curves) of the first component, \psi_1 are circles about our arbitrarily chosen origin of radius r, and those of \psi_2 are rays extending from the origin at angle \theta. The coordinate curves are still happen to cross each other at right angles, as were the Cartesian ones, but we could, in principle, have chosen a coordinate system where they cross at other angles.
*
Now, suppose we have an arbitrary curve in the Euclidean plane, perhaps representing the orbit of a planet. The planet's velocity at any point along this curve is represented by a tangent vector (rather than a displacement vector), which can be visualised as a directed line segment (little arrow) pointing in the direction of motion. Its speed is the magnitude of this vector. Where does this kind of vector live? There's a separate vector space associated with each point, P, of the Euclidean plane, called the tangent space at that point, T_p, the space of all possible tangent vectors at that point, i.e. all possible velocities. Just as we're free to chose any coordinates we like for the Euclidean plane itself, so we can chose any coordinates we like for the tangent spaces. The coordinates of a vector are its components, the coefficients by which the basis vectors must be scaled so that their sum equals that vector. So a choice of "coordinates for vectors" is a choice of basis.
One obvious choice is to use the coordinate basis associated with whichever coordinate system is being used on the plane, \mathbb{E}^2, itself. That is, let the basis vectors of each tangent space be the tangent vectors ("velocity vectors") of the coordinate curves at that point, i.e. parameterise the curves by arc length, and their tangent vectors are their derivtives with respect to arc length. In Euclidean space with Cartesian coordinates, this gives us an identical, right-handed orthonormal basis for the tangent space at each point.
Another choice of bases is the one you mention where polar coordinates are being used on the Euclidean plane. In this method, the basis for the tangent space at each point is taken to be a unit vector, \hat{\textbf{r}}, tangent to the line of constant theta through that point, and a unit vector \hat{\pmb{\theta}} (there should be a hat on that, but it doesn't show up for some reason...), tangent to the circle of constant radius through that point. Because the coordinate curves are at right angles to each other in polar coordinates, the basis vectors are at right angles to each other at each point. The big difference between these and Cartesian coordinate bases is that these orthonormal bases vary from point to point.
In elementary courses and texts, the following three things are often identified: the Euclidean plane itself, a Cartesian coordinate system for the plane, and the tangent spaces at every point of the plane. Only when other coordinate systems are introduced does it become necessary to consider them as distinct concepts. It doesn't help that the word "(reference) frame" sometimes means a coordinate system on the underlying set of points, while "frame" can also mean a field of basis vectors for the tangent spaces. Another variation to watch out for is that some people use the word "Euclidean space" for the affine space of points in \mathbb{E}^2, as described above, while others use it for the vector space with vectors in \mathbb{R}^2. It's perfectly possible to develop these ideas taking the set of pairs of real numbers as the underlying set of points on which coordinate systems are defined. In that case, there exists one natural choice of coordinate function: the identity function.
These ideas are developed further in the subject of differential geometry, where the concept of a manifold occurs as a generalisation of Euclidean space.
)
