$\DeclareMathOperator\Ann{Ann}\DeclareMathOperator\Tr{Tr}$My answer is somewhat complementary to Nik Weaver's, and admitedly more focused on Question 2 since I have nothing more to add to the latter regarding Question 1.
When you deal with a not necessarily commutative C${}^*\!$-algebra $\mathfrak{A}$, the Riesz representation theorem is no longer the tool one uses to represent states. What is usually done is the so-called Gel'fand–Naimark–Segal (GNS) construction of a ${}^*\!$-representation $\pi_\omega:\mathfrak{A}\rightarrow\mathfrak{B}(\mathscr{H}_\omega)$ of $\mathfrak{A}$ in a Hilbert space $\mathscr{H}_\omega$ starting from a state $\omega$ on $\mathfrak{A}$.
Let us recall the GNS construction for convenience. We assume for now that $\mathfrak{A}$ has a unit $\mathbb{1}$. Recall that a state on $\mathfrak{A}$ is a linear map $\omega:\mathfrak{A}\rightarrow\mathbb{C}$ such that $\omega(a^*a)\geq 0$ for all $a\in\mathfrak{A}$ and $\omega(\mathbb{1})=1$. This implies that $$\mathfrak{A}\times\mathfrak{A}\ni(a,b)\mapsto\omega(a^*b)$$ is a positive semidefinite Hermitian sesquilinear form on $\mathfrak{A}$, and therefore satisfies the Cauchy–Schwarz inequality $$\lvert\omega(a^*b)\rvert^2\leq\omega(a^*a)\omega(b^*b)\leq\|a\|^2\omega(b^*b)\ ,\quad a,b\in\mathfrak{A}\ $$
(the latter inequality comes from the fact that $b=\|a\|^2\mathbb{1}-a^*a$ is a positive element of $\mathfrak{A}$, i.e. it has the form $b=c^*c$ for some $c\in\mathfrak{A}$) This means that the so-called annihilator $\Ann \omega$ of $\omega$ $$\Ann \omega=\{a\in\mathfrak{A} \mathrel\vert \omega(a^*a)=0\}$$ is a left ideal (hence a vector subspace) of $\mathfrak{A}$, consisting of the zero-seminorm elements of $\mathfrak{A}$ with respect to the seminorm $\|\cdot\|_\omega$ on $\mathfrak{A}$ induced by this sesquilinear form: $$\|a\|_\omega=\sqrt{\omega(a^* a)}\ ,\quad a\in\mathfrak{A}\ .$$ Hence, the latter induces a complex scalar product on $\mathfrak{A}/\Ann \omega$ - if $[a],[b]$ are the respective equivalence classes of $a,b\in\mathfrak{A}$ modulo $\Ann \omega$, we write $$\langle[a],[b]\rangle=\omega(a^*b)\ .$$ Moreover, since $\Ann \omega$ is a left ideal, $\mathfrak{A}$ has a natural left action on $\mathfrak{A}/\Ann \omega$ as $$\pi_\omega(a)[b]=[ab]\ .$$ This defines a ${}^*\!$-representation $\pi_\omega$ on $\mathfrak{A}/\Ann \omega$ which satisfies $$\|\pi_\omega(a)[b]\|\leq\|a\|\,\|[b]\|=\|a\|\,\|b\|_\omega\ ,\quad a,b\in\mathfrak{A}\ ,$$ thanks to the Cauchy–Schwarz inequality. This means that $\pi_\omega$ extends uniquely to a ${}^*\!$-representation of $\mathfrak{A}$ in the Hilbert space $\mathscr{H}_\omega=\overline{\mathfrak{A}/\Ann \omega}$ by bounded linear operators therein. The state $\omega$ is then represented in $\mathscr{H}_\omega$ by the unit-norm element $\Omega_\omega=[\mathbb{1}]$, for $\omega(a)=\langle\Omega_\omega,\pi_\omega(a)\Omega_\omega\rangle$ for all $a\in\mathfrak{A}$.
As you can see, the GNS construction "kind of" identifies $\mathfrak{A}$ with (a dense subspace of) the Hilbert space $\mathscr{H}_\omega$ - that is, modulo $\Ann \omega$. If the state is faithful, i.e. $\Ann \omega=\{0\}$, then $\mathfrak{A}$ is indeed identified with (a dense subspace of) $\mathscr{H}_\omega$ - this is equivalent to $\pi_\omega$ being injective, i.e. faithful, and to $\pi_\omega$ being isometric. This happens regardless of $\mathfrak{A}$ having Hilbert-Schmidt elements or not. However, even though any nonzero C${}^*\!$-algebra possesses a good deal of faithful states (this is a consequence of the Hahn-Banach theorem and leads to the important Gel'fand-Naimark theorem identifying abstract C${}^*\!$-algebras with closed ${}^*\!$-subalgebras of bounded linear operators in a Hilbert space), not all states of $\mathfrak{A}$ are faithful.
Depending on which kind of C${}^*\!$-algebra $\mathfrak{A}$ and reference state $\omega$ you have, another given state $\eta$ on $\mathfrak{A}$ may or may not be representable as trace-class operators $\rho_\eta$ in $\mathscr{H}_\omega$ with unit trace, that is, given a linear map $\eta:\mathfrak{A}\rightarrow\mathbb{C}$ such that $\eta(a^*a)\geq 0$ for all $a\in\mathfrak{A}$ and $\eta(\mathbb{1})=1$ there may or may not be a $0\leq\rho_\eta\in\mathfrak{B}(\mathscr{H}_\omega)$ with $\Tr(\rho_\eta)=1$ such that $\eta(a)=\Tr(\rho_\eta\pi_\omega(a))$ for all $a\in\mathfrak{A}$.
A situation where this is true regardless of which $\omega$ you choose is when $\mathfrak{A}$ is finite dimensional (i.e. a ${}^*\!$-algebra of matrices). This remains true for $\mathfrak{A}=\mathfrak{B}(\mathscr{H})$ with a separable Hilbert space $\mathscr{H}$ - i.e. a type-I factor (as mentioned at the end of Nik Weaver's answer), which is the case of the algebra of observables for physical systems with finitely many degrees of freedom. On the other hand, for the kind of C${}^*\!$-algebras that appear as algebras of observables for physical systems with infinitely many degrees of freedom (e.g. thermodynamic limits of quantum statistical systems and quantum field theory), this is usually false — as examples, one may cite thermal equilibrium states at different temperatures (in the thermodynamic limit), distinct pure thermodynamic phases of a non-pure thermal equilibrium state, different superselection sectors in quantum field theory, etc.
In physical terms, infinitely many degrees of freedom usually is a manifestation of locality. More precisely, one usually considers the self-adjoint elements of $\mathfrak{A}$ as local observables measured within certain space(-time) regions (or limits of Cauchy sequences thereof). This means that states $\eta$ of the form $\eta(a)=\Tr(\rho_\eta\pi_\omega(a))$ may be seen as states "accessible" from $\omega$ through "physically allowed local operations", at least to an arbitrary degree of accuracy. Any other state is seen as "disjoint" from $\omega$. In infinitely extended space(-time) regions, there are usually plenty of mutually disjoint states on $\mathfrak{A}$.
