The state is a vector in the Hilbert space of the Hamiltonian, which gives it a natural basis in terms of the eigenvectors; distinct eigenvalues then exist in distinct (orthogonal) subspaces - for degenerate values the subspaces are larger, but they are still distinct from all others. Clearly this situation gives many advantages in analysis.
However, this representation, though natural, and dependent only upon the spectral decomposition of the Hamiltonian, is not unique. The experimentalist will prefer to establish a basis which corresponds to his experimental setup! Chosing a different basis will change all of the coordinates, but does not change the states.
To make this clear recall that the state vectors of our Hilbert space can also be viewed a as rays, which are similar to the geometric rays of Euclidean geometry. Imagine the ray first, then superimpose a grid upon it - as you rotate the grid about the origin of the ray the intersections of the grid with the ray define the coordinates for that basis. The coordinates change, but the ray doesn't change. For ordinary geometry the relationships between two rays (angles, projections) don't change, so it is clear that some relationships between the coordinates are fixed - these are properties of a metric space.
Our Hilbert space is a normed space - distances don't mean anything, but a normalized state vector always has a length of 1, even when you change the basis; nor does the length change under unitary operators - hence their name.
All of this becomes clear in a good linear algebra course.
This is a good question, and the answer is rather subtle, and I think a physicist and a mathematician would answer it differently.
Mathematically, a Hilbert space is just any complete inner product space (where the word "complete" takes a little bit of work to define rigorously, so I won't bother).
But when a physicist talks about "the Hilbert space of a quantum system", they mean a unique space of abstract ket vectors $\{|\psi\rangle\}$, with no preferred basis. Exactly as you say, you can choose a basis (e.g. the position basis) which uniquely maps every abstract state vector $|\psi\rangle$ to a function $\psi(x)$, colloquially called "the wave function". (Well, the mapping actually isn't unique, but that's a minor subtlety that's irrelevant to your main question.)
The confusing part is that this set of functions $\{\psi(x)\}$ also forms a Hilbert space, in the mathematical sense. (Mumble mumble mumble.) This mathematical Hilbert space is isomorphic to the "physics Hilbert space" $\{|\psi\rangle\}$, but is conceptually distinct. Indeed, there are an infinite number of different mathematical "functional representation" Hilbert spaces - one for each choice of basis - that are each isomorphic to the unique "physics Hilbert space", which is not a space of functions.
When physicists talk about "the Hilbert space of square-integrable wave functions", they mean the Hilbert space of abstract state vectors whose corresponding position-basis wave functions are square integrable. That is:
$$\mathcal{H} = \left \{ |\psi\rangle\ \middle|\ \int dx\ |\langle x | \psi \rangle|^2 < \infty \right \}.$$
This definition may seem to single out the position basis as special, but actually it doesn't: by Plancherel's theorem, you get the exact same Hilbert space if you consider the square-integrable momentum wave functions instead.
So while "the Hilbert space of square integrable wave functions" is a mathematical Hilbert space, you are correct that technically it is not the "physics Hilbert space" of quantum mechanics, as physicists usually conceive of it.
I think that in mathematical physics, in order to make things rigorous it's most convenient to consider functional Hilbert spaces instead of abstract ones. So mathematical physicists consider the position-basis functional Hilbert space as the fundamental object, and define everything else in terms of that. But that's not how most physicists do it.
Best Answer
Observables aren’t a basis of the Hilbert space: their eigenvectors form a basis. The strategy is to find the largest possible set of commuting operators, so that their common eigenvectors are uniquely labelled by the eigenvalues in the commuting set. In your example, the Hilbert space is 2-dimensional and the eigenvalues of $\hat S_z$ are $\pm \frac{1}{2}$, so that’s enough to uniquely label the basis of your Hilbert space, so you don’t need anything else.
In your example, you could choose your basis vector $(1,0)^\top$ and $(0,1)^\top$ to be the eigenvectors of $\hat S_x$, and this would be just as fine: the matrix representation of $\hat S_z$ and $\hat S_y$ would then be non-diagonal.
The dimension of the Hilbert space is tied to the number of distinct mutually exclusive outcomes: experiment shows there’s only 2 possible distinct outcomes to measuring the spin of a spin-1/2 particle, and since these outcomes do not depend on the direction, the basis states of any operator of the form $$ n_x\hat S_x+n_y\hat S_y+n_z\hat S_z\, \qquad n_x^2+n_2^2+n_z^2=1 $$ would could serve as a basis for the 2-dimensional Hilbert space. It is convention to chose a basis where $\hat S_z$ is diagonal, but that’s just convention.