I had the same question, when studying the subject. Let me tell you, what I was told - it relates to the functional calculus:
Recall that in quantum mechanics, as we usually learn it, a measurement is a projective measurement, i.e. the outcomes of a measured observables are eigenvalues of the observable and we "update" the state according to the knowledge obtained (i.e. we project it into the Hilbert space). We can of course use the whole formalism of POVMs instead if you know about this, but still, projective measurements remain important special cases. For this reason, we don't actually need our Hermitian observables, but we need the spectral calculus and the spectral theorem. You want all spectral projections of an observable to belong to your space, since if you measure the observable, your results will be updated according to the eigenprojections. And here is the problem: C*-algebras in generally do not contain all their projections, von Neumann algebras do. So the "physical consequence" is that you actually have all your measureable quantities inside the algebra of operators you call "observables". I believe that is as physical as it gets. Since von Neumann algebras can always be seen as closures of C*-algebras in some topology, I would not expect there to be a much deeper reasons, although I'd love to know them myself, if there are.
Other reasons mentioned to me refer to the structure of von Neumann algebras (and its lattice of projections) and how this enters different scenarios in physics, but in this case, I would say that the reason to study von Neumann algebras is rather technical than physical.
Finally, let me point out that it is not a priori clear why we should study C*-algebras at all - I mean, the only physical quantities are the Hermitian operators, but generically, our algebras will contain many nonhermitian elements. In my view, this means there is no reason to study either C*-algebras or von Neumann algebras, but one would actually have to study Jordan algebras (the set of Hermitian elements of the bounded operators on some Hilbert space forms such a Jordan algebra, or more precisely, a Jordan operator algebra). Since these algebras are however nonassociative (which is inconvenient) and can nearly always be embedded into some associative algebra, we study the associative algebras. So, in a sense, studying C*-algebras is already "a technical thing".
There are many approaches. But first I want to make sure you know that when you have $n$ spin zero particles in a 3d space and have a wavefunction that the function is from $\mathbb R^{3n},$ i.e. from configuration space. But also I want you to know when someone says infinite dimensional Hilbert Space, they mean the size of a set of mutually orthonormal vectors.
Now when you have some particles and know their spin you could start with a specific concrete set of wavefunctions from configuration space into a tensor product of the spin states. You can then use the inner product on the spin states to get an inner product of the wavefunctions. And this is basically like picking a basis when do vector analysis.
Given the wavefunctions you could then talk about the operators. The operators form a vector space, then have a norm defined on them, they have an adjoint operation. And some times $A-\lambda I$ is not invertible as an operator (for instance when $\lambda$ is an eigenvalue of $A$). And it is possible to reverse the process.
So if you start with a bunch of things that act like operators, i.e. that form a vector space, that have a multiplication, have a norm, have a star operator and they satisfy the rules you'd expect. Then you can call it a $C^*$ algebra. Then it turns out the standard assumptions in mathematics assert that there is a Hilbert space and a subset of the operators on the Hilbert space that as a vector space with a multiplication, a norm, and the adjoint (as the star operator) will act just like your $C^*$ algebra.
So you can start with a Hilbert Space and then define operators. Or you can start with a $C^*$ algebra and then define your Hilbert Space as one of the Hilbert Spaces that has a subalgebra of operators just like your $C^*$ algebra. The biggest deal is knowing how to connect to experimental results since either way you have an algebra, some operators and a Hilbert Space and any triple you have is going to look like the other triple you made starting from the other end.
As for a spectrum. Since the algebra has a multiplication you can discuss whether $A-\lambda I$ is invertible without needing to have vectors that are eigen to any operators, the object just have an inverse or it doesn't, from the set of things you can multiply.
You could imagine messing with matrices, adding, scaling, multiplying, taking adjoints. And discussing whether they have inverses, without every mentioning that there are vectors the matrices could act on. And then you can be more abstract and say the fact they are matrices wasn't important, just have things with a scaling operation, a norm operation, and adjoint operation, and a multiplication operation, that do the right things.
How does one choose a Hilbert space to associate with a system?
You could start with it, or start with your algebra. Or you can focus on connecting a Hilbert Space with the outcomes of certain experimental results. For instance the completion of the set of eigenvectors for a maximal set of compatible measurements.
How does one deal with this ambiguity given by that theorem?
Having different vector spaces that correspond to your physical setup is no worse than being able to choose your x y and z axis to point any direction you want in the lab. Truly no different. They are all isomorphic, and 3d vector space. And it isn't a problem.
If the observables determine the space, how does this happen if one can only define the operators after knowing the space?
The algebra doesn't need the space. You can have a bunch of square matrices without having column or row vectors. You can have the algebra with the scaling, adding, multiplying, morning, and adjointing without having the matrices. And you still can have a spectrum.
Best Answer
UPDATE: the insights and conceptual meanings advocated below in this answer are detailed and technically developed, for example, in these wonderful articles:
For intuitions and insights on the meaning of the formalism of quantum mechanics, I eagerly recommend you read carefully the following wonderful reference books (especially Feynman on intuition and examples, Isham on the meaning of mathematical foundations, and Strocchi or Blank et al. on the $C^*$-algebras approach):
As Feynman said (something similar): "If you think you understand quantum mechanics then you do not understand it at all". The whole issue of understanding its Hilbert space formalism, aside from the interpretation of the physical theory itself, can be dealt with more easily (in fact, that is what most physicists do: understand the mathematical formalism with "naïve" empirical intuitions of its meaning so that the theory is predictive and useful, but the issue of its real ontology and epistemology is not at all settled yet). The best approach to grasp the quantum formalism may be to give a parallel interpretation of its classical mechanics analogue, so I will try to elaborate this a bit regarding your different points you mention. Note that quantum mechanics and its postulates can be formulated in different equivalent forms: Dirac's bra-ket formulation of Schrödinger's picture (wave mechanics), Heisenberg's operator formulation (matrix mechanics) and the density operator formulation of states (in Heisenberg's picture). Since your different points are very intertwined, I will try to explain a little bit of everything all at once.
In classical mechanics one measures empirical quantities like the position and speed (so linear momentum) of bodies and idealized particles, thus defining a configuration space and phase space of all physical possible states. Any other observable property must be a function of the system intrinsic parameters (usually constants like rest mass, charge...) and those dynamical variables, so the algebra of classical observables (like Energy) is the commutative ring of typical functions on phase space. Given a measurement one constrains the system to a localized region of phase space within the instrumental precision available, thus obtaining the inicial conditions of the system of interests (where the rest of the universe is usually either ignored or put into an effective/statistical external action over the relevant degrees of freedom). After much experimental observation, physicists obtained the "dynamic laws of classical mechanics" by which given that initial observed state, the system shall evolve with respect to an external clock variable, so at a later time its new observed state can be predicted within the restrictions of precision and chaos theory.
Quantum mechanics is the experimental realization that at the microscopic level, the degrees of freedom of any system behave differently. Classical observables, like position and linear momentum arise as a large scale statistical result of their quantum mechanical counterparts. Concretely, phase space is not commutative (Heisenberg's uncertainty bound) so classical position and momentum define a minimum "quantum chunk" of phase space. Thus, as functions of these noncommutative basic observables, the rest of quantum observables (with classical counterpart) must come from generically noncommuting operators, and these act naturally on Hilbert spaces.
Points 1 & 3 have really the same justification. One assumes that any real experiment, i.e. any empirical observation made by any instrument and read by any sentient being, measures real numbers: position is located by distances to reference systems, timing is kept track with periodic movements also so speed and then momentum all reduce to movement measurements in the end (masses are measured for example with the distance of stretching of a spring by which an object is hung). So observables must give real values upon measurement, which because of precision errors are actually approximated by rationals, or even computable reals, in practice. Now, one can think of an observable as the set of possible values of it, i.e. the set of different possible states of a measurable property. If our quantum mechanical observables must be in general noncommutative operators and be totally specified by a spectrum of real values, then the natural choice is to consider self-adjoint operators since operators have a real eigenvalue spectrum in a suitable basis if and only if they are self-adjoint. So quantum mechanics is "just" the transition to operators which are not simultaneously diagonal in the same basis. This is the significance of the spectral decomposition theorem for the whole formalism: a quantum observable is just the set of its possible classical empirical values codified as an operator by a spectral decomposition with these values as eigenvalues. Thus, all the quantum observables must be self-adjoint operators, with the quantumness manifesting itself by the general noncommutativity of them. Self-adjoint operators which are diagonalizable in the same eigenbasis are said to be "compatible", and they are so if and only if they commute with each other (that is why commutators $[A,B]$ play such an important role in the formalism). The fact of existing noncommuting sets of operators, like position and linear momentum, was called "complementarity" by Bohr.
Point 2 & 4 is just the mathematical realization of all the previous discussion. Since classical observables form a commutative $C^*$-algebra, and quantum observables a noncommutative $C^*$-algebra, by the Gel'fand-Naimark theorem any of the latter is isometrically isomorphic to an algebra of (bounded) linear operators in some Hilbert space. This is a practical realization of the abstract concept of observables as being sets of values and having general algebraic relations between them, i.e. a kind of calculational representation. Once the Hilbert space is introduced, the Gel'fand-Naimark-Segal construction shows that pure states correspond then to rays in the Hilbert space (i.e. to vectors/point of the projective Hilbert space). This corresponds to the quantum case of the classical situation were the abelian version of Gel'fand-Naimark states that every commutative $C^*$-algebra (with unity) is isometrically isomorphic to the algebra of continuous functions for some compact Hausdorff space, thus recovering phase space. This establishes the kinematics of the theory, after which dynamics can be introduced and studied by either evolving states with operators fixed (Schrödinger's picture) or evolving operators with states fixed (Heisenberg's picture), and these are dual to each other. In the statistical physics point of view, when a system is in a given state, all one really measures about an observable is its expectation value with respect to the probability distribution of that state; thus, a state can be viewed as a positive linear functional on the $C^*$-algebra of observables (not to be confused with the functionals given by Dirac's "bras" discussed below), establishing the duality between states and operators: a "state" is a probability distribution on the algebra, determining the probability of possible values of any observable in the next measurement, now by Gleason's theorem any such distribution implies the existence of a density operator which represents a pure (or more generally mixed) state of the system. Thus, you can either see a pure state as an eigenvector of a complete set of compatible observables, or either a positive linear functional on their algebra. This is very deep and important because removes any ontological weight to the state vectors beyond the mere fact of being "the collection of probabilities of possible actualization of values" of the system.
Point 4 can now be understood naturally. When measuring observables, the instruments are localizing "where in the spectrum of eigenvalues" the system has each property. If measuring a particular observable has no effect on the value of another, then they are compatible, and by exhausting the measurements of a complete set of compatible observables for a system, one specifies the state of the system at that moment: since our system is characterized by the properties we observe, particular defined properties for each of its features characterizes the system completely. Since by measuring compatible observables we are selecting eigenvalues in the spectrum of the operators, we are actually projecting from the complete Hilbert space down to a particular vector labeled by the eigenvalues, as a complete set of commuting self-adjoint operators define a common eigenbasis. Thus the "string of data of observed values" is our measured observed state, so one thinks of the vector (ket $|\psi\rangle$) as the pure state of the system. Since predictions of the theory do not depend on the norm of the vector, the state of the system is actually a ray, i.e. a vector in the projective Hilbert space. (In fact since this must be done also for continuous spectrum of unbounded self-adjoint operators, the right formalism is that of rigged Hilbert spaces). Therefore, each (ray) vector basis of the Hilbert space corresponds to a choice of which set of compatible observables one is measuring, with each vector of each basis being a possible state to get in observations, i.e. a possible array of (eigen)values of our chosen properties to measure and characterize the system. In between observations, the isolated system evolves unitarily, so the "hidden" state of the system gets into a general superposition of eigenvectors in any chosen eigenbasis. Besides the duality on the operator-state level, there is the other dual notion of "bra" $\langle\psi|$ which are the linear functionals on the vectors of Hilbert space. Do not confuse Hilbert vector states, their vectorial duals as final states, and the state seen as a positive linear functional on the algebra of observables: the pure measurable states $|\psi\rangle$ are given by eigenstates in a common eigen-basis of commuting self-adjoint operators, and general states as a superposition of those; now since most of the prediction of the formalism are given by the Hilbert scalar products of vector states, $(|\psi\rangle,\, |\chi\rangle)$, the Riesz representation theorem guarantees that there is a functional $\phi_\psi:\mathcal H\rightarrow\mathcal C$ such that $\langle\psi|\chi\rangle :=\phi_\psi(|\chi\rangle)=(|\psi\rangle,\, |\chi\rangle)$, so Dirac rewrote the whole formalism in terms of bras $\langle\chi|$ and kets $|\chi\rangle$ to denote things like the probability amplitud to observe the sate $|\psi\rangle$ after having observed state $|\chi\rangle$, so: $\mathcal P(\chi\rightarrow\psi)=|\langle\psi|\chi\rangle |^2$. Since probabilities are scalar products squared, if $\chi$ or $\psi$ are linear superpositions of other eigenstates, the transition probability is not the sum of individual possibilities but there are also cross terms which are responsible for the interference quantum effects and the wave-particle duality. So you can think of bras, the functionals, as "final states" in a calculation.
The fundamental experimental fact is that there are properties which cannot be measured simultaneously (not even in perfect ideal conditions). If one measures the position of an atom, one gets a region in $\mathbb R^3$ more localized/small as more precise is the measurement device, but then the measurement of its linear momentum spreads in size over the possible values. Of course each measured value is as precise and definite as possible, but if you repeat the position measurement after the momentum one, the old value is not conserved and position randomly takes a new value within its spectrum, with a probabilistic distribution of dispersion/variance bigger as smaller is the uncertainty in momentum. What is happening is not a mysterious magic, but the fact that position and momentum operators do not commute, so they do not have a common eigenbasis, thus the system cannot be at the same time in a defined position and defined momentum. It is an old philosophical misconception that the act of observing by perturbing the system alters the value and makes simultaneous measurements impossible, complementarity is one of the core features of the quantum world regardless of who or what makes a measurement. Since "a state" is a set of defined properties of our system, there is no meaning to talking about simultaneously defined incompatible observables, in the same sense as there is no meaning in talking about the color of a music note (putting aside synesthesia). The confusion appears for trying to conceptualize the quantum world within classical realism (structural empiricism is much better in this regard). After the observation was made, if the system is allowed to evolve in isolation again, the theory predicts the probability of observing another possible eigenstate, maybe from another basis, at a later time. The formalism does this by evolving the initial observed eigenstate into a general linear superposition by Schrödinger's equation, so at a later time the complex components of the evolved vector over every eigenstate of any chosen basis have changed, with the square of the modulus of each component being the probability for observing the eigenvalues of that eigenvector. This is Schrödinger's picture, which is misleading philosophically (as Dirac himself claimed!), from an empiricist stance the more meaningful picture is Heisenberg's: the state is only the observed state, the ket characterized by the string of observed (eigen)values of a chosen set of compatible observables; when the system is isolated, its observables/operators evolve unitarily, the state does not change until observed again, but the new observation gives randomly new values as the operators have changed. Thus the whole formalism can be cast into operator algebras, with observables and states characterized by specific types of operators (as the states themselves can be seen as the projections of the spectral decomposition in a common eigenbasis, so if you just measure some of the compatible observables your state is a projector not into an eigenvector but into a common eigen-subspace of your chosen set of compatible observables).
SUMMARY: Systems are completely described by the observable properties they have, which may not be simultaneously defined. This is because having defined properties of certain kinds makes impossible to have defined properties of another kinds, so observing some aspects of a system destroys/"undefines" the previous properties which are incompatible with the new ones. This forces the algebra of observables to be noncommutative: the order of which observables are measured in succession does not necessarily commute. Since any physical measurement is numerical, in general real-valued, the noncommutative algebra fits nicely among self-adjoint operators, as they are the only unitarily equivalent to a real spectrum. Thus, we determine experimentally which sets of observables commute, so we can talk of complete sets of compatible operators, which define the state of the system completely by a string of eigenvalues (the actual values of the parameters/properties measured). Such a set defines a basis of a Hilbert space upon which the operators act, so different sets of compatible operators define different basis, so that if our system is given by a common eigenvector of one basis, it will be generally a linear superposition of the eigenvectors of another basis; since the eigenvalues are the observable properties of the system, the superposition in the other basis has no uniquely defined eigenvalues and thus those properties of the system in that state are not well-defined at that time. Since common eigenstates can be given by projection operators which project onto the successive eigensubspaces, a (pure) state of the system can be given either by a ray, by a suitable projection operator on the Hilbert space, or by a positive linear functional on the noncommutative $C^*$-algebra of quantum observables. One can work only with operator algebras and characterize which are observables and which are states and interrelate them by linear evaluations to get the predictions of the theory (mostly expectation values).