The answer to your first question is no, and here is the reason.
Note that the identity mapping
$$
i:A\to L^2_\phi(A)
$$
is continuous. Thus, if $A=L^2_\phi(A)$, the open mapping theorem
implies that $i$ is an isomorphism and hence $A$ is seen to be isomorphic$^{(1)}$ to a Hilbert space. This would in turn imply
that every closed subspace of $A$ is also isomorphic to some Hilbert space.
This said, choose some self adjoint element $a$ in $A$ with infinite spectrum (these exist in any infinite dimensional
$C^*$-algebra) and consider the closed $^*$-subalgebra $C^*(a)\subseteq A$ generated by $a$. It is well known that $C^*(a)$ is
isometrically isomorphic to $C_0(\sigma (a)\setminus\{0\})$, so we conclude that $C_0(\sigma (a)\setminus\{0\})$ is
isomorphic to some Hilbert space.
However it is a well known fact that $C_0(X)$ is not isomorphic to a Hilbert space for every infinite locally compact
space $X$.
$^{(1)}$ Two normed spaces $E$ and $F$ are said to be isomorphic if there exists a map $T:E\to F$ which is linear, bijective, continuous, and whose inverse is continuous. If $T$ is moreover isometric, then we say that $E$ and $F$ are isometrically isomorphic.
A key part of the story here is that a $C^*$-algebra whose self-adjoint elements all have finite spectrum must be finite-dimensional. Martin Argerami gave a reference which implies this result by way of several more general results in the context of Banach algebras. However, I decided to write up an account specifically for the $C^*$-algebra case in order to take advantage of the simplifications this context has to offer.
Claim 1: Suppose $A$ is a unital $C^*$-algebra all of whose self-adjoint elements have one point spectrum. Then $A$ is one-dimensional.
Sketch: Use functional calculus to show every self-adjoint element is a multiple of $1_A$, then use the fact that every $C^*$-algebra is the span of its self-adjoint part.
Claim 2: Let $A$ be a $C^*$-algebra in which every self-adjoint element has a finite spectrum and let $p$ be a nonzero projection in $A$ such that the "corner algebra" $pAp$ is not one dimensional. Then, one can write $p=p_1+p_2$ where $p_1$ and $p_2$ are nonzero, orthogonal projections.
Sketch: Working inside $pAp$, whose unit is $p$, the previous claim gives a self-adjoint element whose spectrum is a finite set with at least two elements. Now use functional calculus.
Claim 3: Let $A$ be unital $C^*$-algebra all of whose self-adjoint elements have finite spectrum. Then there exist nonzero, pairwise orthogonal projections $p_1,\ldots,p_n$ summing to $1_A$ such that each of the corner algebras $p_iAp_i$ is one-dimensional.
Sketch: If $A$ is not one-dimensional, subdivide $1_A$ into two projections. If either of the new projections does not determine a one-dimensional corner, subdivide again. This process must eventually terminate and give a decomposition of the desired type. Otherwise, we would have an infinite collection of pairwise orthogonal projections in $A$ which could then be used to embed a copy of $c_0(\mathbb{N})$ into $A$ leading to self-adjoint elements of infinite spectrum, contrary to assumption.
Claim 4: Let $p$ and $q$ be nonzero, orthogonal projections in a $C^*$-algebra $A$ satisfying that $pAp$ and $qAq$ are one-dimensional. Then $qAp$ and $pAq$ are either both one-dimensional or both zero.
Proof: Since $(qAp)^* = pAq$, it suffices to look at $qAp$. Fix any nonzero $a \in qAp$. By the $C^*$-identity, $a^*a \in pAp$ and $aa^* \in qAq$ are nonzero. Since $pAp$ is one-dimensional, up to rescaling $a$, we may assume $a^*a=p$. But then $a$ is a partial isometry, so $aa^*$ is also a projection and, being a nonzero projection in $qAq$, is equal to $q$. The identities $a^*a=p$ and $aa^*=q$ show that $x \mapsto ax : pAp \to qAp$ and $x \mapsto a^* x : qAp \to pAp$ are mutually inverse bijections, and the result follows.
Claim 5: Let $A$ be a unital $C^*$-algebra and let $p_1,\ldots,p_n$ be (necessarily orthogonal) projections satisfying $1_A=p_1 + \ldots + p_n$. Then, $A$ is the internal direct sum of the spaces $p_i A p_j$ where $1 \leq i,j \leq n$.
Basically, each element of $A$ can be thought of as a "matrix of operators" with respect to this partition of the identity.
Final Claim: Let $A$ be a $C^*$-algebra all of whose self-adjoint elements have finite spectrum. Then, $A$ is finite-dimensional.
Proof: First unitize $A$ if necessary (which does not affect the spectra of any of its elements). Then combine Claims 3, 4 and 5.
Best Answer
Adding the assumption that you're asking about Banach $*$-algebras with isometric involution, your question Why is $\ell^1(\mathbb{Z})$ not a $C^{*}$-algebra? has the example $\ell^1(\mathbb Z)$.
Another is the algebra of bounded analytic functions on the unit disk with sup norm and involution $f^{*}(z)=\overline{f(\overline z)}$.
You mention matrices, and implicitly you seem to be assuming that $M_n$ is given the operator norm from acting as operators on $\mathbb C^n$ with the standard inner product, or equivalently $\|a\|=\sqrt{\text{the spectral radius of }a^*a}$, where $a^*$ is the conjugate transpose of $a$. But if you give $M_n$ another submultiplicative norm that makes the conjugate transpose norm-preserving, then you will not have a $C^*$-algebra. One example is the Frobenius norm, a.k.a. the Hilbert–Schmidt norm, $\|a\|=\sqrt{\mathrm{Trace}(a^*a)}$.
You say that the upper-triangular matrices satisfy the $C^*$-identity, but it is not clear what that means when they don't have an involution. If you are asking about $*$-algebras, then subalgebras of $*$-algebras that are not closed under the involution are out of the picture.
The first example above, $\ell^1(\mathbb Z)$, fits into a bigger picture of considering the Banach $*$-algebra $L^1(G)$ of a locally compact Hausdorff group $G$ with Haar measure, which sometimes arises in the study of group representations.
One thing that makes $\ell^1(\mathbb Z)$ more interesting than $M_n$ with the Frobenius norm as an example is that $\ell^1(\mathbb Z)$ is not even isomorphic as an algebra to any $C^*$-algebra.