My favourite proof is due to Hartig:
D. G. Hartig, The Riesz representation theorem revisited, American Mathematical Monthly, 90(4), 277–280.
Hartig claims that his proof is ...category-theoretic but having unwrapped the details I must say it is really functional-analytic. The idea is as follows.
Step 1. We can easily prove this theorem for extremely
disconnected compact Hausdorff spaces. Indeed, everything can be
reduced there to messing around with indicator functions of clopen subsets.
Step 2. We employ the Stone–Čech compactification of a discrete
space. One can use the Banach–Alaoglu theorem to show that every completely
regular space admits the Stone–Čech compactification. The Stone–Čech
compactification of a discrete space is extremely disconnected.
Step 3. Now, we prove that every compact space $X$ is a continuous
image of an extremely disconnected space. Indeed, give $X$ the
discrete topology. Call this space $X_d$ and extend the identity map
$\iota \colon X_d \to X$ to a continuous map from $\beta X_d$ to $X$.
Then, transfer the Riesz theorem to $X$ via the adjoint map to $f\mapsto f\circ (\beta\iota)$ ($f\in C(X)$).
The main difference is that in the first case, the functional is defined on the space of continuous functions (on a compact set) whereas in the second case the functional operates on the integrable functions.
For completeness' sake, I add that there also exists a version for continuous functions for which the integration is performed with respect to a measure. This result is much more general than the ones you mentioned, but in your case, the measure theoretic version and the one with a BV-function are essentially the same. The reason for this is that to each signed measure $\mu$ on an interval corresponds a function with bounded variation $g$ (and vice versa) such that the Riemann-Stieltjes-integral of a continuous function $f$ with respect to $g$ coincides with the Lebesgue-integral of $f$ with respect to $\mu$. See this post for some details.
As for the measure-theoretic versions, whether you have to use a real (i.e. signed) measure or a complex measure just depends on whether your functional is real- or complex-valued. This will most often coincide with whether your continuous/integrable functions are real- or complex-valued, since a linear functional is typically defined to be a linear mapping from a vector space into the underlying scalar field, which can only be $\mathbb{R}$ in the case of real-valued functions.
The Riesz theorem for Hilbert spaces is, although named the same, a completely different story. This theorem is about the interplay of continuous functionals and the inner product whereas the other theorems are concerned with the representation of functionals by means of an integral. The deeper similarity of all of them is that they offer characterisations of a dual space.
EDIT: As pointed out by Martin Argerami, the last paragraph is incorrect, I quote:
Any Hilbert space can be represented as $H=L^2(X, \mu)$ for an appropriate measure space $X$, and so the Riesz Representation Theorem says that you can write a bounded functional $\phi$ by$$\phi(f)=\langle f,g\rangle = \int_X f\,\bar g\,d\mu.$$
Therefore, there is a much more immediate similarity between the Riesz theorems.
Best Answer
Folland's proof (Theorem 7.2 in 1st edition Real Analysis) is quite conceptual, though in total the proof takes about 2.5 pages. The idea suggesting that this theorem should be true is very simple, though; the bulk of the proof is checking that the idea doesn't just give you a measure, but a Radon measure whose associated linear functional on $C_c(X)$ is the one you started with.
The idea is that $X$ being locally compact and Hausdorff implies (via Urysohn's lemma) that we can approximate the characteristic function of any open subset of $X$ from both above (when the closure is compact) and below (always) by continuous, compactly supported functions. This lets us define a measure for any continuous linear functional.
More precisely, for any open subset $U \subset X$, the characteristic function $\chi_U$ satisfies $$ \chi_U(x) = \sup_{f: U \to [0, 1]} f(x), $$ where of course I'm restricting to $f \in C_c(X)$. Then if $\psi \in C_c(X)^*$, we define the $\psi$-measure of $U$ to be $$ \mu_\psi(U) = \sup_{f: U \to [0, 1]} \psi(f). $$ Since the Borel $\sigma$-algebra is generated by open subsets, this suffices to define $\mu_\psi(E)$ for any Borel set $E \subset X$ (via Caratheodory's theorem).
As mentioned in the comments, checking that this definition gives a Radon measure, and $\int \, f \, d\mu_\psi = \psi(f)$ requires some work and estimates, but nothing quite as nitty-gritty as $\varepsilon-\delta$ arguments. I think by construction $\mu_\psi$ looks promisingly like it will be inner-regular, at least. It may even look promising that in the case $\overline{U}$ is compact, we could use an $\inf$ over $f \in C_c(X)$ with $f \ge \chi_U$ above when defining $\mu_\psi(U)$ and get the same value. I'll leave it to your imagination (or to Folland's) to check $\int\,f\,d\mu_\psi = \psi(f)$.